[Kombinatoryka] Takie grafowe
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
-
- Użytkownik
- Posty: 867
- Rejestracja: 12 kwie 2008, o 13:35
- Płeć: Mężczyzna
- Podziękował: 6 razy
- Pomógł: 78 razy
[Kombinatoryka] Takie grafowe
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.
-
- Użytkownik
- Posty: 53
- Rejestracja: 21 lut 2011, o 20:49
- Płeć: Mężczyzna
- Lokalizacja: Skierniewice
- Pomógł: 10 razy
-
- Użytkownik
- Posty: 867
- Rejestracja: 12 kwie 2008, o 13:35
- Płeć: Mężczyzna
- Podziękował: 6 razy
- Pomógł: 78 razy
[Kombinatoryka] Takie grafowe
JaQb pisze:Ukryta treść:
odpowiedź:
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.JaQb pisze: Moje rozwiązanie:Ukryta treść:
-
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
[Kombinatoryka] Takie grafowe
Nie widzę dlaczego to łatwo widać. Czy można prosić o wyjaśnienie?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]}\).
- Swistak
- Użytkownik
- Posty: 1874
- Rejestracja: 30 wrz 2007, o 22:04
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 99 razy
- Pomógł: 87 razy
[Kombinatoryka] Takie grafowe
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.
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Cactus_graph