Teorema della colorazione di Konig.

Messaggioda 3m0o » 06/12/2019, 16:56

Se \(G \) è un grafo bipartito e sia \( \Delta(G) \) il grado massimo dei sui vertici, allora \( \Delta(G) \) è uguale al numero minimo di colori necessari, denotato con \(m \) a colorare ciascun arco di \(G \) in modo tale che nessun arco adiacente abbia lo stesso colore.

Una direzione è facile infatti se \( m < \Delta(G) \) allora sia \( v \) il vertice corrispondente al grado massimo, abbiamo che da \(v \) escono esattamente \( \Delta(G) \) archi tutti adiacenti, pertanto non possiamo colorare tutti gli archi uscenti da \(v \) con colori differenti. Dunque \( m \geq \Delta(G) \) , per l'altra ho più problemi.
Supponiamo \( m > \Delta(G) \).
Sia \( G = (V,E) \) il nostro grafo e sia \( V= A \cup B \) la bipartizione di \( G \)
Siano \(M_1, M_2, \ldots, M_{\Delta(G)} \) gli insiemi corrispondenti archi colorati tutti dello stesso colore. Ovvero tutti gli archi in \(M_1 \) ad esempio sono rossi. Sappiamo che per ipotesi abbiamo che esiste \( e = (v,u) \) dove \( v \in B \) e \(u \in A \) e tale che \[ e \not\in \bigcup\limits_{i=1}^{\Delta(G)} M_i \]
\( \operatorname{deg}(u)\leq \Delta(G) \) pertanto che esiste \( M_i \), e diciamo che sia \(M_1 \) tale che nessun arco in \(M_1 \) sia connesso con \( u \).
Analogamente \( \operatorname{deg}(v)\leq \Delta(G) \) pertanto che esiste \( M_i \), e diciamo che sia \(M_2 \) tale che nessun arco in \(M_2 \) sia connesso con \( v \).

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.

Se posso affermare queste cose sopra allora posso invertire i ruoli di \( M_1 \) e di \( M_2 \) all'interno del path \( P \), e creare due nuovi insiemi \(M_1' \) e \( M_2 ' \).
Ora abbiamo che sia \( u \) che \( v \) non sono connessi a nessun arco che sta in \( M_2' \) pertanto abbiamo che possiamo colorare \( e = (v,u) \) con il colore di \(M_2' \) e questo contraddice il fatto che \( m > \Delta(G) \).

Vi sembra possa funzionare?
3m0o
Average Member
Average Member
 
Messaggio: 618 di 827
Iscritto il: 02/01/2018, 15:00

Re: Teorema della colorazione di Konig.

Messaggioda 3m0o » 09/12/2019, 14:19

Nessuno riesce ad aiutarmi? :)
3m0o
Average Member
Average Member
 
Messaggio: 629 di 827
Iscritto il: 02/01/2018, 15:00

Re: Teorema della colorazione di Konig.

Messaggioda Martino » 09/12/2019, 17:24

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 \).
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)$.

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?
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 7489 di 7550
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Re: Teorema della colorazione di Konig.

Messaggioda 3m0o » 09/12/2019, 19:45

Martino ha scritto:
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 \).
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) $.

No perché sto supponendo per assurdo che il numero minimo di colori, indicato con \(m \) sia strettamente più grande di \( \Delta(G) \). pertanto se diciamo che i colori sono \( M_1 , \ldots, M_{\Delta(G)} , M_{\Delta(G)+1}, \ldots, M_{m} \).
Se \( \deg (u) < \Delta(G) \) allora per forza di cose esiste un colore tra i \( M_1 , \ldots, M_{\Delta(G)} \) che non viene utilizzato. Mentre se \( \deg(u) = \Delta(G) \) allora esiste un colore tra tutti \( M_1 , \ldots, M_{\Delta(G)} , M_{\Delta(G)+1}, \ldots, M_{m} \), che non viene utilizzato, semplicemente gli scelgo il nome e dico che è \( M_1 \).
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?

No la mia domanda è se posso affermare le cose scritte da me
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.

Perché in caso affermativo mi sembra che la dimostrazione sia completa e non parziale, ma magari mi sbaglio. Non volevo guardare una dimostrazione già fatta perché volevo provare a farla per conto mio.
3m0o
Average Member
Average Member
 
Messaggio: 631 di 827
Iscritto il: 02/01/2018, 15:00

Re: Teorema della colorazione di Konig.

Messaggioda Martino » 09/12/2019, 21:46

Ok ho capito cosa vuoi dire.
3m0o ha scritto:Possiamo suppore che vi sia un arco in \(M_2 \) connesso con \(u \) ?
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.

Ma l'argomento che segue (quello col path) non l'ho capito.

A me sembra una dimostrazione confusionaria, non è più facile costruire una colorazione con $Delta(G)$ colori? Tipo:

Testo nascosto, fai click qui per vederlo
Se i colori sono $1,...,t=Delta(G)$ e i vertici sono $v_1,...,v_k$ allora coloriamo gli archi connessi a $v_1$ coi colori $1,...,j_1$ dove $j_1$ è il grado di $v_1$ e coloriamo gli archi connessi a $v_i$ e non ancora colorati ciascuno col minimo dei colori non ancora usati. Si tratta di una colorazione ammissibile perché se due archi sono adiacenti allora, essendo il grafo bipartito, hanno un vertice in comune quindi i loro colori sono distinti per costruzione. E se a un certo punto avessimo bisogno di un colore in più ci troveremmo di fronte a un vertice di grado maggiore di $Delta(G)$.
Le persone che le persone che le persone amano amano amano.
Avatar utente
Martino
Moderatore globale
Moderatore globale
 
Messaggio: 7490 di 7550
Iscritto il: 21/07/2007, 10:48
Località: Brasilia

Re: Teorema della colorazione di Konig.

Messaggioda 3m0o » 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.

Allora effettivamente è confusa questa parte, cerco di spiegarmi meglio.
Consideriamo il sottografo \( M_1 \cup M_2 \). In \( M_1 \cup M_2 \) il grado di ogni vertice è al massimo 2. In particolare il grado di \( u \) e \( v \) è 1. Quindi \( M_1 \cup M_2 \) è l'unione disgiunta di paths e cicli.
Sia \( P \) il path che contiene \( u \). \(P \) ha archi di colori alterni. Partendo da \( u \) (che dev'essere un estremità del path in quanto ha grado 1) coloriamo gli archi con \( M_2 \) poi con \( M_1 \) etc.
\( v \) può essere contenuto in \( P \)? Direi di no, ma non sono sicuro.
Se \(v \) non è contenuto in \(P \) possiamo scambiare i colori degli archi in \( P \). E concludere la prova perché possiamo colorare \( (u,v) \) con il colore \( M_2 \).
3m0o
Average Member
Average Member
 
Messaggio: 632 di 827
Iscritto il: 02/01/2018, 15:00


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Overflow94 e 7 ospiti