Un grafo bilanciato
Definizioni:
In un grafo (finito) con gli archi orientati, indichiamo con $deg(X)$ il numero di archi che partono dal nodo $X$.
Sia $A$ 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, ... , X_k$ in modo tale che esista un arco orientato da $X_i$ a $X_{i+1}$ per $1 <= i <= 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.
In un grafo (finito) con gli archi orientati, indichiamo con $deg(X)$ il numero di archi che partono dal nodo $X$.
Sia $A$ 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, ... , X_k$ in modo tale che esista un arco orientato da $X_i$ a $X_{i+1}$ per $1 <= i <= 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.
Risposte
Probabile che faccio confusione o tralascio parecchi casi a quest'ora 
Forse è sufficiente dimostrare che il massimo non può diminuire e il minimo non può aumentare.
Considero allora tutti i percorsi inizialmente uscenti da un massimo. I loro nodi avranno o grado massimo o grado "massimo -1" altrimenti il percorso sarebbe cattivo. Adesso qualunque siano gli archi che inverto: se aumento il grado di uno di quei nodi il problema non si pone. Se invece diminuisco il grado di uno di quei nodi vuol dire che ho rigirato un arco che usciva da un "massimo" o "massimo -1" e andava verso un altro "massimo" o "massimo-1". Quindi quel che perdo da una parte lo ritrovo dall'altra. Alla fine quindi tutti i percorsi che partono da massimi non possono diminuire il loro numero complessivo di archi e poichè la loro media è compresa tra "massimo" e "massimo-1" ci sarà almeno un nodo sopra media che sarà almeno un "massimo". E lo stesso ragionamento (dovrebbe (?)) andare anche con i percorsi che entrano nei minimi.
Forse è sufficiente dimostrare che il massimo non può diminuire e il minimo non può aumentare.
Considero allora tutti i percorsi inizialmente uscenti da un massimo. I loro nodi avranno o grado massimo o grado "massimo -1" altrimenti il percorso sarebbe cattivo. Adesso qualunque siano gli archi che inverto: se aumento il grado di uno di quei nodi il problema non si pone. Se invece diminuisco il grado di uno di quei nodi vuol dire che ho rigirato un arco che usciva da un "massimo" o "massimo -1" e andava verso un altro "massimo" o "massimo-1". Quindi quel che perdo da una parte lo ritrovo dall'altra. Alla fine quindi tutti i percorsi che partono da massimi non possono diminuire il loro numero complessivo di archi e poichè la loro media è compresa tra "massimo" e "massimo-1" ci sarà almeno un nodo sopra media che sarà almeno un "massimo". E lo stesso ragionamento (dovrebbe (?)) andare anche con i percorsi che entrano nei minimi.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo