Un grafo bilanciato

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Un grafo bilanciato

Messaggioda fram » 29/06/2014, 9:22

Definizioni:
In un grafo (finito) con gli archi orientati, indichiamo con $deg(X)$ il numero di archi che hanno origine (partono) nel nodo $X$.
Sia $A$ il nodo (/uno dei nodi) con grado massimo nel grafo, sia $B$ un nodo di grado minimo.
Chiamiamo valore del grafo la differenza $deg(A)-deg(B)$.
Il grafo è bilanciato quando, invertendo il verso di alcuni archi, non è possibile ottenere un grafo di valore minore.
Chiamiamo percorso una sequenza di nodi $X_1, X_2, \dots , X_k$ in modo tale che esista un arco orientato da $X_i$ a $X_{i+1}$ per $i = 1 \dots k-1$.
Se $deg(X_1) > deg(X_k) + 1$, il percorso si dice cattivo.
Il grafo è bello se non ha al suo interno nessun percorso cattivo.

Problema:
Dimostrare che se un grafo è bello allora è bilanciato.
fram
 
Messaggi: 6
Iscritto il: 15/04/2014, 20:45

Re: Un grafo bilanciato

Messaggioda Delfad0r » 31/03/2016, 23:14

Prendiamo un grafo $G$ sbilanciato, e dimostriamo che è brutto.
Il grafo è sbilanciato, quindi è possibile ottenere, invertendo alcuni archi, un grafo $G'$ con valore strettamente minore di quello di $G$. Chiamiamo $deg'(X)$ il grado di un nodo $X$ nel grafo trasformato $G'$.
Deve necessariamente verificarsi uno dei seguenti: il grado massimo di $G'$ è minore di quello di $G$, oppure il grado minimo di $G'$ è maggiore di quello di $G$; se ciò non accadesse, allora il valore di $G'$ sarebbe maggiore o uguale di quello di $G$. Distinguiamo dunque due casi.
  • Il grado massimo diminuisce.
    Sia $A$ un nodo di $G$ di grado massimo $k$.
    Coloriamo di rosso gli archi che si invertono da $G$ a $G'$ e (muovendoci sempre in $G$), coloriamo di rosso tutti i nodi che si possono raggiungere da $A$ camminando solo su archi rossi; notiamo che deve esserci almeno un arco rosso uscente da $A$, altrimenti il suo grado non potrebbe diminuire. Consideriamo quindi il sottografo $T$ composto da tutti i nodi rossi (fra cui è incluso $A$) e dagli archi rossi incidenti a due nodi rossi. Per ogni nodo $X$ in $T$, chiamiamo $in(X)$ il numero di archi di $T$ entranti in $X$, e $out(X)$ il numero di archi di $T$ uscenti da $X$. Notiamo che vale $deg'(X)\ge deg(X)-out(X)+in(X)$, perchè gli archi rossi si invertono, e tutti gli archi rossi uscenti da $X$ stanno sicuramente in $T$.
    Vale $k=deg(A)$, e $k>deg'(A)\ge deg(A)-out(A)+in(A)=k-out(A)+in(A)$ (ricordiamo che il grado massimo di $G'$ è minore di quello di $G$), quindi $in(A)-out(A)<0$. Ma
    $$
    \sum_{v\in T}(in(v)-out(v))=0
    $$
    poichè ogni arco in $T$ ha entrambi gli estremi in $T$, quindi la somma dei gradi uscenti è uguale a quella dei gradi entranti. Pertanto deve esistere un nodo $V\in T$ tale che $in(V)-out(V)>0$, da cui segue che $k>deg'(V)\ge deg(V)+in(V)-out(V)\ge deg(V)+1$, cioè $k=deg(A)>deg(V)+1$. Per come abbiamo definito $T$, esiste un percorso da $A$ a $V$, quindi $G$ è brutto.
  • Il grado minimo aumenta.
    Questo caso è praticamente analogo al precedente. Si costruisce il grafo $T$ dei nodi da cui è possibile raggiungere $B$ (un nodo di grado minimo in $G$) usando solo archi rossi; si nota che $deg'(X)\le deg(X)-out(X)+in(X)$ e che $h=deg(B)<deg'(B)\le deg(B)-out(B)+in(B)$, da cui $in(B)+out(B)>0$, quindi esiste $V\in T$ tale che $in(B)+out(B)<0$, da cui $h<deg'(V)\le deg(V)-out(V)+in(V)\le deg(V)-1$, cioè $deg(V)>deg(B)+1$, perciò $G$ è brutto.


Testo nascosto:
Necroposting like there is no tomorrow :mrgreen:
Delfad0r
 
Messaggi: 191
Iscritto il: 09/02/2015, 22:19


Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti