Trzy zadania z teorii grafów.

[wiku94]

Cześć, bardzo proszę o pomoc przy tych zadankach:

1) Wykazać, że w każdym grafie liczba wierzchołków nieparzystego stopnia jest parzysta.

2) Wielomianem chromatycznym grafu \(\displaystyle{ G}\) jest wielomian \(\displaystyle{ P_{G}(x) = x^{5} - 9x^{4} + 29x^{3} - 39x^{2} + 18x}\). Wyznaczyć liczbę chromatyczną \(\displaystyle{ X(G)}\).

3) Wykazać, że jeśli graf G ma n wierzchołków \(\displaystyle{ (n \ge 3)}\) i \(\displaystyle{ d_{G}(x) + d_{G}(y) \ge n}\) dla każdych dwóch niesąsiednich wierzchołków \(\displaystyle{ x}\) i \(\displaystyle{ y}\), to \(\displaystyle{ G}\) jest grafem Hamiltona.

[PiotrowskiW]

Do pierwszego użyj indukcji matematycznej. (względem wierzchołków)
Nie pamiętam nomenklatury teorii grafów.

W pierwszym kroku weźmy "ten graf liniowy z dwoma wierzchołkami i jedną krawędzią".
Ustalmy n i załóżmy (założenie indukcyjne), że mamy graf z danymi 2n-wierzchołkami o stopniach nieparzystych.
Weźmy wierzchołek v i "dołączmy" go do grafu.
Wówczas mamy jedną z dwóch sytuacji:
a) połączyliśmy go 2k krawędziami z wierzchołkami nieparzystych stopni.
b) połączyliśmy go 2l+1 krawędziami z wierzchołkami nieparzystych stopni
c) połączyliśmy go 2m krawędziami z wierzchołkami nieparzystych stopni.
d) połączyliśmy go 2p+1 krawędziami z wierzchołkami nieparzystych stopni
gdzie \(\displaystyle{ k,l,m,p \in N \cup \left\{ 0\right\}}\)
i każde z nich jest mniejsze od n.
Chyba to jakoś tak pójdzie.

[matmatmm]

W pierwszym kroku weźmy "ten graf liniowy z dwoma wierzchołkami i jedną krawędzią".

W kroku pierwszym powinien być graf złożony z jednego wierzchołka albo nawet graf bez wierzchołków.

Ustalmy n i załóżmy (założenie indukcyjne), że mamy graf z danymi 2n-wierzchołkami o stopniach nieparzystych.

Założenie indukcyjne powinno wyglądać tak, że zakładamy, że dla każdego grafu o \(\displaystyle{ n}\) wierzchołkach zachodzi teza.

Weźmy wierzchołek v i "dołączmy" go do grafu.

Zamiast dołączać wierzchołek do jakiegoś grafu powinniśmy ustalić graf o \(\displaystyle{ n+1}\) wierzchołkach, usunąć z niego jeden wierzchołek i zastosować założenie indukcyjne do powstałego grafu o \(\displaystyle{ n}\) wierzchołkach.

Wówczas mamy jedną z dwóch sytuacji:
a) połączyliśmy go 2k krawędziami z wierzchołkami nieparzystych stopni.
b) połączyliśmy go 2l+1 krawędziami z wierzchołkami nieparzystych stopni
c) połączyliśmy go 2m krawędziami z wierzchołkami nieparzystych stopni.
d) połączyliśmy go 2p+1 krawędziami z wierzchołkami nieparzystych stopni
gdzie \(\displaystyle{ k,l,m,p \in N \cup \left\{ 0\right\}}\)
i każde z nich jest mniejsze od n.
Chyba to jakoś tak pójdzie.

Tej części nie rozumiem. Ja bym moje rozumowanie kontynuował robiąc drugą indukcję względem liczby krawędzi wychodzących z usuniętego wierzchołka.

-- 29 sie 2014, o 17:36 --

Przemyślałem sprawę i stwierdzam, że dużo można to zrobić dużo prościej za pomocą pojedynczej indukcji po liczbie krawędzi.

[PiotrowskiW]

W kroku pierwszym powinien być graf złożony z jednego wierzchołka albo nawet graf bez wierzchołków.

Graf musi mieć co najmniej jeden wierzchołek, żeby można to było nazwać grafem.

Zamiast dołączać wierzchołek do jakiegoś grafu powinniśmy ustalić graf o n+1 wierzchołkach, usunąć z niego jeden wierzchołek i zastosować założenie indukcyjne do powstałego grafu o n wierzchołkach.

Dlaczego?

[matmatmm]

Tak naprawdę usuwając, czy dodając, to wychodzi w tym przypadku na to samo, ale chciałem to zrobić w pełni poprawnie pod względem logicznym. Otóż dowodzimy twierdzenia:
Dla każdego \(\displaystyle{ n\in\NN}\) dla każdego grafu o \(\displaystyle{ n}\) wierzchołkach liczba wierzchołków stopnia nieparzystego jest parzysta.
Widać stąd, że naszą funkcją zdaniową zależną od \(\displaystyle{ n}\) jest: Dla każdego grafu o \(\displaystyle{ n}\) wierzchołkach liczba wierzchołków stopnia nieparzystego jest parzysta.
Dalej chyba nie muszę tłumaczyć.-- 29 sie 2014, o 18:48 --A tak w ogóle to najlepiej to zrobić indukcją po liczbie krawędzi.

[kapsl0k]

1) Wykazać, że w każdym grafie liczba wierzchołków nieparzystego stopnia jest parzysta.

Nie wiem, czy miałeś to twierdzenie na wykładzie, ale nawet jeśli nie, to je tutaj udowodnimy.

Tw. Suma stopni wierzchołków w grafie jest równa podwojonej liczności zbioru krawędzi.

\(\displaystyle{ \sum_{v \in V} deg(v) = 2|E|}\)

Dowód (zdroworozsądkowy): Każda krawędź ma dwa końce, a dodając stopnie obydwu wierzchołków incydentnych z tą krawędzią liczymy ją podwójnie.


Tw. W każdym grafie liczba wierzchołków nieparzystego stopnia jest parzysta.

Dowód: Jeśli by tak nie było, tzn. liczba wierzchołków nieparzystego stopnia byłaby nieparzysta, to i suma wszystkich stopni w tym grafie byłaby nieparzysta, a tak, zgodnie z wcześniejszym twierdzeniem, zdarzyć się nie może, bo wtedy liczność zbioru krawędzi nie byłaby liczbą naturalną.

3) Wykazać, że jeśli graf G ma n wierzchołków \(\displaystyle{ (n \ge 3)}\) i \(\displaystyle{ d_{G}(x) + d_{G}(y) \ge n}\) dla każdych dwóch niesąsiednich wierzchołków \(\displaystyle{ x}\) i \(\displaystyle{ y}\), to \(\displaystyle{ G}\) jest grafem Hamiltona.

To jest po prostu twierdzenie Orego. Odsyłam do Wikipedii, gdzie dowód jest przedstawiony: