06/12/2019, 16:56
09/12/2019, 14:19
09/12/2019, 17:24
Non ho capito questa affermazione. Come segue dalla definizione di $Delta(G)$? Potrebbe essere che per ogni $i=1,...,Delta(G)$ esista un arco in $M_i$ connesso a $u$. No? In questo caso $u$ avrebbe grado $Delta(G)$.3m0o ha scritto:pertanto che esiste \( M_i \), e diciamo che sia \(M_1 \) tale che nessun arco in \(M_1 \) sia connesso con \( u \).
09/12/2019, 19:45
Martino ha scritto:Non ho capito questa affermazione. Come segue dalla definizione di $ Delta(G) $? Potrebbe essere che per ogni $ i=1,...,Delta(G) $ esista un arco in $ M_i $ connesso a $ u $. No? In questo caso $ u $ avrebbe grado $ Delta(G) $.3m0o ha scritto:pertanto che esiste \( M_i \), e diciamo che sia \( M_1 \) tale che nessun arco in \( M_1 \) sia connesso con \( u \).
Martino ha scritto:Più in generale mi sembra che tu abbia scritto un inizio di dimostrazione e ci stia chiedendo di completarla. Non è più facile riportare tutta la dimostrazione (presa da un libro o dalla pagina wikipedia del teorema di Konig) e dirci quali punti non ti sono chiari?
3m0o ha scritto:Possiamo suppore che vi sia un arco in \( M_2 \) connesso con \( u \) ?
Se si allora consideriamo gli archi \( M_1 \cup M_2 \). Da cui possiamo estrarre un path \( P= (e_1,\ldots,e_j) \) di archi colorati solo con \( M_1 \) e \( M_2 \), dove \( e_{2n+1} \in M_1 \), e \( e_{2n} \in M_2 \) per ogni \( n \) tale che \( 1 \leq 2n+1, 2n \leq j \) in modo tale che le due estremità siano contenute in \( A \). Se \( u \) è un vertice di questo path \( P \), allora \( v \) non lo è perché l'unico modo in cui \( u \) e \( v \) appartengono a \( P \) è che siano le estremita poiché altrimenti sarebbero connessi con un arco di colore rispettivamente \( M_1 \) e \( M_2 \) e contraddice le ipotesi.
09/12/2019, 21:46
Se nessun arco $M2$ è connesso a $u$ e nemmeno a $v$ allora puoi cambiare colore a $(u,v)$ colorandolo col colore $M2$, e procedi per induzione sul numero massimo di archi che puoi colorare usando solo $Delta(G)$ colori. Mi sembra funzionare.3m0o ha scritto:Possiamo suppore che vi sia un arco in \(M_2 \) connesso con \(u \) ?
11/12/2019, 16:00
3m0o ha scritto:
Da qui in poi non sono sicuro delle affermazioni che posso fare
Possiamo suppore che vi sia un arco in \(M_2 \) connesso con \(u \) ?
Se si allora consideriamo gli archi \( M_1 \cup M_2 \). Da cui possiamo estrarre un path \( P= (e_1,\ldots,e_j) \) di archi colorati solo con \(M_1 \) e \(M_2 \), dove \( e_{2n+1} \in M_1 \), e \( e_{2n} \in M_2 \) per ogni \( n \) tale che \( 1 \leq 2n+1, 2n \leq j \) in modo tale che le due estremità siano contenute in \( A \). Se \(u \) è un vertice di questo path \( P \), allora \( v \) non lo è perché l'unico modo in cui \( u \) e \( v \) appartengono a \( P \) è che siano le estremita poiché altrimenti sarebbero connessi con un arco di colore rispettivamente \( M_1 \) e \( M_2 \) e contraddice le ipotesi.
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.
Powered by phpBB © phpBB Group - Privacy policy - Cookie privacy
phpBB Mobile / SEO by Artodia.