[Teoria grafów] skojarzenie, graf dwudzielny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: matinf »

Witam,

Udowodnij, że każdy spójny, regularny graf dwudzielny jest dwuspójny. Podaj przykład pokazujący, że założenie o dwudzielności jest istotne.

Jest napisane jedynie, że graf jest regularny, ale nie jest napisane jakiego stopnia. Więc ja powiem, że jest \(\displaystyle{ r-}\)regularny - nie tracąc ogólności.

Mamy fakt: skoro jest dwudzielny i \(\displaystyle{ r}\)-regularny to istnieje kolorowanie za pomocą \(\displaystyle{ r}\) kolorów (krawędziowe). Konsekwentnie każdy wierzchołek jest incydenty z każdym kolorem - bo kolorów jest tyle co "wartość" każdego stopnia (bo graf jest regularny).

Wobec tego twierdzę, że graf ma \(\displaystyle{ r}\) skojarzeń doskonałych. Bo mogę powiedzieć, że wybierając krawędzie każdego koloru z osobna mamy skojarzenie doskonałe. Wniosek jest taki, że każda krawędź należy do pewnego skojarzenia doskonałego. I teraz mogę spróbować pokazać, że jeśli każda krawędź należy do jakiegoś skojarzenia doskonałego, to w grafie nie ma punktu artykulacyjnego (co jest równoważne z tym, że jest dwuspójny).

To o co proszę, to sprawdzenie dotychczasowego rozumowania. Czy mogę je kontynuować ? Wszystko dotychczas jest ok ?
kapsl0k
Użytkownik
Użytkownik
Posty: 28
Rejestracja: 13 kwie 2012, o 18:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 2 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: kapsl0k »

Twierdzenie jest fałszywe dla \(\displaystyle{ r=1}\), bo wtedy masz maksymalnie dwa wierzchołki i jedną krawędź. Graf jest spójny, dwudzielny, regularny, a jednak wystarczy usunąć jedną krawędź żeby go rozspójnić.

Podejrzewam jednak, że zależy Ci na przypadkach \(\displaystyle{ r\geq 2}\). W takim wypadku Twoje rozumowanie wydaje mi się poprawne, aczkolwiek nie widzę jeszcze w jaki sposób byś miał dokończyć dowód, ale chętnie go zobaczę.

Mała podpowiedź: dla \(\displaystyle{ r=2k}\) dwuspójność masz za darmo, bo wtedy, na mocy tw. Eulera, istnieje w grafie cykl Eulera, a cykl taki nie zawiera mostów (bo gdyby zawierał, to mielibyśmy dwie składowe połączone mostem i cykl przechodząc przez most nie mógłby już nim wrócić, więc mostów nie ma), więc jest dwuspójny.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: matinf »

Twierdzenie jest fałszywe dla \(\displaystyle{ r=1}\), bo wtedy masz maksymalnie dwa wierzchołki i jedną krawędź. Graf jest spójny, dwudzielny, regularny, a jednak wystarczy usunąć jedną krawędź żeby go rozspójnić.
Tak, dokładnie. Przypominam jednak, że definicji dwuspójności nie dotyczy usuwania krawędzi , tylko wierzchołka + jego krawędzie.

Ale ten przypadek jest trywialny, zakładamy, że \(\displaystyle{ r\ge 2}\).

Ta Twoja rada jest faktycznie prawdziwa, ale dotyczy mostów, a nie punktów artykulacyjnych. Więc nie mamy pewności czy na pewno jest też tak jak dla mostów. Dwuspójność dotyczy wierzchołków.

Ok, czyli spróbuję pokazać. Zakładamy, że każda krawędź należy do jakiegoś skojarzenia doskonałego.
Powiedzmy przeciwnie, że \(\displaystyle{ v}\) jest wierzchołkiem rozpójniającym na dwie spójne: \(\displaystyle{ A\ i\ B}\).
Wówczas skoro graf jest spójny w obu spójnych istnieją wierzchołki, które mają połączenie do \(\displaystyle{ v}\): \(\displaystyle{ v_A,v_B}\).
Rozważmy krawędź \(\displaystyle{ vv_B}\). Wówczas biorąc skojarzenie z tą krawędzią, wszystkie wierzchołki w \(\displaystyle{ A}\) muszą się nawzajem skojarzyć. Czyli liczba wierzchołków w \(\displaystyle{ A}\) jest parzysta. Skoro tak, to teraz weźmy skojarzenie, które zawiera krawędź \(\displaystyle{ vv_A}\). I znowu wierzchołki w \(\displaystyle{ A}\) muszą się nawzajem pokojarzyć, ale teraz liczba wierzchołków tam jest nieparzysta, a więc nie możemy ich skojarzyć - co jest sprzeczne z założeniem o istnieniu skojarzenia doskonałego. Czyli wierzchołek \(\displaystyle{ v}\) nie może być punktem artykulacyjnym.
kapsl0k
Użytkownik
Użytkownik
Posty: 28
Rejestracja: 13 kwie 2012, o 18:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 2 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: kapsl0k »

Przypominam jednak, że definicji dwuspójności nie dotyczy usuwania krawędzi , tylko wierzchołka + jego krawędzie.
Ja znam dwie definicje \(\displaystyle{ k}\)-spójności: krawędziową i wierzchołkową. Większość zadań, które robiłem, była na krawędziową właśnie, dlatego musisz mi wybaczyć, chociaż trochę tu Twojej winy, bo nie sprecyzowałeś.
wszystkie wierzchołki w A muszą się nawzajem skojarzyć.
Tego zdania nie rozumiem. Wszystkie nawzajem, znaczy każdy z każdym, a przecież graf jest dwudzielny, więc jeśli zawiera więcej niż jeden wierzchołek z jednej klasy dwudzielności, to pomiędzy nimi nie ma żadnej krawędzi. Chodzi Ci po prostu o to, że istnieje skojarzenie doskonałe?

Poza tym nie rozumiem dalszej części dowodu. Jeśli \(\displaystyle{ v}\) jest wierzchołkiem rozspójniającym, to go wyrzucasz i rozważasz graf \(\displaystyle{ G-v}\), czy zostawiasz? Bo jeśli wyrzucasz, to jest oczywistym, że skojarzenia doskonałego już nie ma (bo jest nieparzysta liczba wierzchołków). Nie wiem dlaczego też istnienie skojarzenia doskonałego w grafie ma w jakikolwiek sposób rzutować na istnienie takiego skojarzenia w podgrafie (przykład: dowolny graf dwudzielny posiadający skojarzenie doskonałe, a podgraf będący jedną z klas dwudzielności takiego nie ma).

Nie widzę też sensu w zdaniu "Weźmy skojarzenie zawierające krawędź \(\displaystyle{ vv_B}\). Twoje dalsze stwierdzenia wyglądają tak, jak byś założył, że każda krawędź należy do dokładnie jednego skojarzenia doskonałego, a wcześniej tego nie napisałeś (stwierdziłeś tylko, że każda należy do pewnego).

Szczerze mówiąc nie przemawia do mnie ten dowód. Możliwe, że jest to poprawne rozumowanie, ale jeśli tak, to są tam duże skoki myślowe, ewentualnie jestem na to zbyt głupi.

Znalazłem jednak inny dowód tego twierdzenia, niewykorzystujący w ogóle skojarzeń. Jeśli chcesz, to skorzystaj, bo do mnie on przemawia: ... -connected
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: matinf »

Spróbuję Ciebie jednak przekonać.
Wiadomo, że każda krawędź należy do jakiegoś skojarzenia doskonałego. Jeśli położę dwie krawędzie:
\(\displaystyle{ v_Av}\) i \(\displaystyle{ vv_B}\) to położyłem również dwa różne skojarzenia doskonałe.

Zakładam nie wprost, że istnieje wierzchołek \(\displaystyle{ v}\), który rozspójnia graf. I ustalam, że rozspójnia na dwie spójne:
\(\displaystyle{ A}\) i \(\displaystyle{ B}\). A to oznacza, że obie te spójne jedyne co mają ze sobą wspólnego to wierzchołek \(\displaystyle{ v}\).
Tzn, mam na myśli to, że nie istnieje krawędź pomiędzy tymi spójnymi.

I teraz mogę powiedzieć, że weźmy skojarzenie, w którym leży krawędź \(\displaystyle{ vv_B}\). Co z pozostałymi wierzchołkami w \(\displaystyle{ A}\) i \(\displaystyle{ B}\) ? Jak w tym skojarzeniu, które wziąłem zostają kojarzone ? (one też muszą w tym skojarzeniu być sparowane, przeto skojarzenie to nic innego jak pewno parowanie). Ale jak powiedziałem, nie ma krawędzi między tymi spójnymi, czyli wszystkie pary dla wierzchołków w \(\displaystyle{ A}\) muszą zostać stworzone w obrębie tej spójnej, czyli jest w niej parzysta ilość wierzchołków.

Teraz dalej - tym razem weźmy skojarzenie doskonałe z krawędzią \(\displaystyle{ v_Av}\). Wówczas nadal nie ma krawędzi pomiędzy dwoma spójnymi. Ale została nam nieparzysta liczba wierzchołków w spójnej \(\displaystyle{ A}\). A skoro nieparzysta to jak niby może istnieć skojarzenie ? Przecież żaden wierzchołek z spójnej \(\displaystyle{ A}\) nie skojarzy się z wierzchołkiem ze spójnej \(\displaystyle{ B}\), zaś w \(\displaystyle{ A}\) to niemożliwe, bo jest nieparzyście wiele wierzchołków. Sprzeczność.
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: Zordon »

matinf pisze: Ok, czyli spróbuję pokazać. Zakładamy, że każda krawędź należy do jakiegoś skojarzenia doskonałego.
Powiedzmy przeciwnie, że \(\displaystyle{ v}\) jest wierzchołkiem rozpójniającym na dwie spójne: \(\displaystyle{ A\ i\ B}\).
Wówczas skoro graf jest spójny w obu spójnych istnieją wierzchołki, które mają połączenie do \(\displaystyle{ v}\): \(\displaystyle{ v_A,v_B}\).
Rozważmy krawędź \(\displaystyle{ vv_B}\). Wówczas biorąc skojarzenie z tą krawędzią, wszystkie wierzchołki w \(\displaystyle{ A}\) muszą się nawzajem skojarzyć. Czyli liczba wierzchołków w \(\displaystyle{ A}\) jest parzysta. Skoro tak, to teraz weźmy skojarzenie, które zawiera krawędź \(\displaystyle{ vv_A}\). I znowu wierzchołki w \(\displaystyle{ A}\) muszą się nawzajem pokojarzyć, ale teraz liczba wierzchołków tam jest nieparzysta, a więc nie możemy ich skojarzyć - co jest sprzeczne z założeniem o istnieniu skojarzenia doskonałego. Czyli wierzchołek \(\displaystyle{ v}\) nie może być punktem artykulacyjnym.
To jest ok, trzeba tylko dodać, że w takim grafie jest parzyście wiele wierzchołków. Poza tym, \(\displaystyle{ A,B}\) niekoniecznie muszą być składowymi, ale rozumowanie przechodzi też bez tego.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: matinf »

Zordon pisze:
matinf pisze: Ok, czyli spróbuję pokazać. Zakładamy, że każda krawędź należy do jakiegoś skojarzenia doskonałego.
Powiedzmy przeciwnie, że \(\displaystyle{ v}\) jest wierzchołkiem rozpójniającym na dwie spójne: \(\displaystyle{ A\ i\ B}\).
Wówczas skoro graf jest spójny w obu spójnych istnieją wierzchołki, które mają połączenie do \(\displaystyle{ v}\): \(\displaystyle{ v_A,v_B}\).
Rozważmy krawędź \(\displaystyle{ vv_B}\). Wówczas biorąc skojarzenie z tą krawędzią, wszystkie wierzchołki w \(\displaystyle{ A}\) muszą się nawzajem skojarzyć. Czyli liczba wierzchołków w \(\displaystyle{ A}\) jest parzysta. Skoro tak, to teraz weźmy skojarzenie, które zawiera krawędź \(\displaystyle{ vv_A}\). I znowu wierzchołki w \(\displaystyle{ A}\) muszą się nawzajem pokojarzyć, ale teraz liczba wierzchołków tam jest nieparzysta, a więc nie możemy ich skojarzyć - co jest sprzeczne z założeniem o istnieniu skojarzenia doskonałego. Czyli wierzchołek \(\displaystyle{ v}\) nie może być punktem artykulacyjnym.
To jest ok, trzeba tylko dodać, że w takim grafie jest parzyście wiele wierzchołków. Poza tym, \(\displaystyle{ A,B}\) niekoniecznie muszą być składowymi, ale rozumowanie przechodzi też bez tego.
(1) Ale w całym grafie ma być parzyście wierzchołków ? Chodzi o istnieje skojarzenia doskonałego ?
(2) Więc całe zadanie jest w porządku ?
(3) Można tutaj indukcje ? Jeśli tak, to jutro spróbuję. Tzn czy indukcja tutaj jest "sensowna"?
kapsl0k
Użytkownik
Użytkownik
Posty: 28
Rejestracja: 13 kwie 2012, o 18:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 2 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: kapsl0k »

matinf pisze:Spróbuję Ciebie jednak przekonać.
Wiadomo, że każda krawędź należy do jakiegoś skojarzenia doskonałego. Jeśli położę dwie krawędzie:
\(\displaystyle{ v_Av}\) i \(\displaystyle{ vv_B}\) to położyłem również dwa różne skojarzenia doskonałe.

Zakładam nie wprost, że istnieje wierzchołek \(\displaystyle{ v}\), który rozspójnia graf. I ustalam, że rozspójnia na dwie spójne:
\(\displaystyle{ A}\) i \(\displaystyle{ B}\). A to oznacza, że obie te spójne jedyne co mają ze sobą wspólnego to wierzchołek \(\displaystyle{ v}\).
Tzn, mam na myśli to, że nie istnieje krawędź pomiędzy tymi spójnymi.

I teraz mogę powiedzieć, że weźmy skojarzenie, w którym leży krawędź \(\displaystyle{ vv_B}\). Co z pozostałymi wierzchołkami w \(\displaystyle{ A}\) i \(\displaystyle{ B}\) ? Jak w tym skojarzeniu, które wziąłem zostają kojarzone ? (one też muszą w tym skojarzeniu być sparowane, przeto skojarzenie to nic innego jak pewno parowanie). Ale jak powiedziałem, nie ma krawędzi między tymi spójnymi, czyli wszystkie pary dla wierzchołków w \(\displaystyle{ A}\) muszą zostać stworzone w obrębie tej spójnej, czyli jest w niej parzysta ilość wierzchołków.

Teraz dalej - tym razem weźmy skojarzenie doskonałe z krawędzią \(\displaystyle{ v_Av}\). Wówczas nadal nie ma krawędzi pomiędzy dwoma spójnymi. Ale została nam nieparzysta liczba wierzchołków w spójnej \(\displaystyle{ A}\). A skoro nieparzysta to jak niby może istnieć skojarzenie ? Przecież żaden wierzchołek z spójnej \(\displaystyle{ A}\) nie skojarzy się z wierzchołkiem ze spójnej \(\displaystyle{ B}\), zaś w \(\displaystyle{ A}\) to niemożliwe, bo jest nieparzyście wiele wierzchołków. Sprzeczność.
Dużo bardziej przejrzyście napisane i mnie przekonuje. Swoją drogą, bardzo ciekawe zadanie, ale i dosyć trudne, ja na pewno nie rozwiązałbym go w ten sposób.
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: matinf »

Dużo bardziej przejrzyście napisane i mnie przekonuje. Swoją drogą, bardzo ciekawe zadanie, ale i dosyć trudne, ja na pewno nie rozwiązałbym go w ten sposób.
Chętnie zobaczę i Twoje rozwiązanie. Możesz nawet przedstawić ten, do którego podałeś linka
kapsl0k
Użytkownik
Użytkownik
Posty: 28
Rejestracja: 13 kwie 2012, o 18:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Pomógł: 2 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: kapsl0k »

(1) Ale w całym grafie ma być parzyście wierzchołków ? Chodzi o istnieje skojarzenia doskonałego ?
(2) Więc całe zadanie jest w porządku ?
(3) Można tutaj indukcje ? Jeśli tak, to jutro spróbuję. Tzn czy indukcja tutaj jest "sensowna"?
Ad.1 Tak, o to chodzi. Dla grafów k-regularnych obydwie klasy dwudzielności muszą być równe, a przez to ilość wierzchołków jest parzysta, bo jest podwojoną licznością którejkolwiek z nich.

Ad.3 A indukcja po czym? Bo po liczbie wierzchołków/krawędzi raczej nie, po \(\displaystyle{ r}\) też by było ciężko. Masz jakiś pomysł, czy tylko tak pytasz?
matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: matinf »

Ad.3 A indukcja po czym? Bo po liczbie wierzchołków/krawędzi raczej nie, po r też by było ciężko. Masz jakiś pomysł, czy tylko tak pytasz?
Pytam kogoś kto wie czy się da, może powiedzieć po czym, a ja sam spróbuje
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

[Teoria grafów] skojarzenie, graf dwudzielny

Post autor: Zordon »

Indukcja to raczej nie jest dobry pomysł.
ODPOWIEDZ