[Kombinatoryka] Takie grafowe

[kaszubki]

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.

[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}\)

[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.

[kaszubki]

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

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.

[Mruczek]

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?

[Swistak]

Każda dwuspójna składowa takiego grafu jest cyklem lub krawędzią, innymi słowy takie grafy to kaktusy

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Cactus_graph

. 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.