[Teoria grafów] skojarzenie, graf dwudzielny
-
- 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
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 ?
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 ?
-
- 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
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.
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.
-
- 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
Tak, dokładnie. Przypominam jednak, że definicji dwuspójności nie dotyczy usuwania krawędzi , tylko wierzchołka + jego krawędzie.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ć.
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.
-
- 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
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ś.Przypominam jednak, że definicji dwuspójności nie dotyczy usuwania krawędzi , tylko wierzchołka + jego krawędzie.
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?wszystkie wierzchołki w A muszą się nawzajem skojarzyć.
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
-
- 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
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ść.
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ść.
- Zordon
- 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
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 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.
-
- 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
(1) Ale w całym grafie ma być parzyście wierzchołków ? Chodzi o istnieje skojarzenia doskonałego ?Zordon pisze: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 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.
(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"?
-
- 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
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 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ść.
-
- 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
Chętnie zobaczę i Twoje rozwiązanie. Możesz nawet przedstawić ten, do którego podałeś linkaDuż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.
-
- 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
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.(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.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?
-
- 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
Pytam kogoś kto wie czy się da, może powiedzieć po czym, a ja sam spróbujeAd.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?