Rozpatrujemy grafy proste o \(\displaystyle{ n}\) wierzchołkach. Znajdź największe takie \(\displaystyle{ m}\), że istnieje graf o \(\displaystyle{ m}\) krawędziach, który nie zawiera cykli o parzystej długości.
[Kombinatoryka] Takie grafowe
: 12 kwie 2012, o 23:29
autor: marcin_smu
Ukryta treść:
Jeśli w grafie 2 różne cykle proste mają wspólną co najmniej jedną krawędź, to istnieją dwa wierzchołki połączone 3 rozłącznymi ścieżkami. Dwie z nich o długości tej samej parzystości tworzą cykl o parzystej długości. Każde 2 różne cykle proste są, więc rozłączne krawędziowo. Nasz optymalny graf jest również spójny(gdyby tak nie było, to dodanie dowolnej krawędzi łączącej 2 różne spójne składowe, nie popsułoby warunków zadania). Usuwając z każdego cyklu dowolną krawędź otrzymamy, więc drzewo o \(\displaystyle{ n-1}\) krawędziach. Pozostaje zastanowić się ile maksymalnie rozłącznych krawędziowo cykli może znajdować się w grafie o \(\displaystyle{ n}\) wierzchołkach. Łatwo widać, że jest to \(\displaystyle{ \left[\frac{n-1}{2}\right]}\). Ostatecznie szukana liczba krawędzi wynosi \(\displaystyle{ \left[ \frac{n-1}{2}\right]+n-1}\)
[Kombinatoryka] Takie grafowe
: 13 kwie 2012, o 09:49
autor: JaQb
Ukryta treść:
Czemu "dodanie dowolnej krawędzi łączącej 2 różne spójne składowe, nie popsułoby warunków zadania"?
Moje rozwiązanie:
Ukryta treść:
Udowodnimy, że szukaną liczbą jest \(\displaystyle{ n}\).
Jeśli graf jest niespójny, analizujemy problem dla spójnych składowych. Jeśli udowodnimy powyższą tezę dla spójnej składowej, udowodnimy ją dla całego grafu.
W grafie 2 różne cykle proste nie mogą mieć wspólnej krawędzi (patrz post wyżej).
Załóżmy, że w spójnej składowej są 2 cykle proste. Wiemy, że:
1) nie mają one wspólnej krawędzi,
2) są połączone pewną ścieżką (prowadzącą z wierzchołka A jednego cyklu do wierzchołka B drugiego cyklu),
3) oba mają nieparzystą długość,
Idziemy: A->1. cykl -> B -> 2. cykl -> A.
Widać, że powyższa ścieżka jest cyklem i ma parzystą długość. Sprzeczność, zatem może istnieć tylko 1 cykl prosty, tak więc krawędzi może być co najwyżej \(\displaystyle{ n}\). Łatwo podać konstrukcję grafu o \(\displaystyle{ n}\) krawędziach spełniającego warunki.
[Kombinatoryka] Takie grafowe
: 13 kwie 2012, o 10:17
autor: kaszubki
JaQb pisze:
Ukryta treść:
Czemu "dodanie dowolnej krawędzi łączącej 2 różne spójne składowe, nie popsułoby warunków zadania"?
odpowiedź:
Jeżeli mamy dwie spójne składowe grafu (dwie spójne, a nie dwuspójne), to dodając krawędź między nimi nie utworzymy żadnego cyklu, więc w szczególności nie utworzymy cyklu o parzystej długości
JaQb pisze:
Moje rozwiązanie:
Ukryta treść:
Udowodnimy, że szukaną liczbą jest \(\displaystyle{ n}\).
Jeśli graf jest niespójny, analizujemy problem dla spójnych składowych. Jeśli udowodnimy powyższą tezę dla spójnej składowej, udowodnimy ją dla całego grafu.
W grafie 2 różne cykle proste nie mogą mieć wspólnej krawędzi (patrz post wyżej).
Załóżmy, że w spójnej składowej są 2 cykle proste. Wiemy, że:
1) nie mają one wspólnej krawędzi,
2) są połączone pewną ścieżką (prowadzącą z wierzchołka A jednego cyklu do wierzchołka B drugiego cyklu),
3) oba mają nieparzystą długość,
Idziemy: A->1. cykl -> B -> 2. cykl -> A.
Widać, że powyższa ścieżka jest cyklem i ma parzystą długość. Sprzeczność, zatem może istnieć tylko 1 cykl prosty, tak więc krawędzi może być co najwyżej \(\displaystyle{ n}\). Łatwo podać konstrukcję grafu o \(\displaystyle{ n}\) krawędziach spełniającego warunki.
Rozwiązanie marcina_smu jest poprawne, więc Twoje nie ;p Problem polega na tym, że cykl składa się z różnych krawędzi.
[Kombinatoryka] Takie grafowe
: 12 sie 2016, o 01:01
autor: Mruczek
marcin_smu pisze: Pozostaje zastanowić się ile maksymalnie rozłącznych krawędziowo cykli może znajdować się w grafie o \(\displaystyle{ n}\) wierzchołkach. Łatwo widać, że jest to \(\displaystyle{ \left[\frac{n-1}{2}\right]}\).
Nie widzę dlaczego to łatwo widać. Czy można prosić o wyjaśnienie?
[Kombinatoryka] Takie grafowe
: 31 sie 2016, o 01:39
autor: Swistak
Każda dwuspójna składowa takiego grafu jest cyklem lub krawędzią, innymi słowy takie grafy to kaktusy
. Stąd łatwo widać, tezę, bo "nie opłaca się" (cudowny zwrot, prawda?) mieć ani wiszących krawędzi, ani krawędzi łączących cykle ani cykli dłuższych niż 3 krawędzie, czyli optymalnie będzie posklejać wierzchołkami trochę trójkątów.