szukanie zaawansowane
 [ Posty: 9 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 24 maja 2016, o 00:34 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
Niech C i D będą różnymi cyklami w grafie G, a e krawędzią wspólną dla cykli C i D. Pokazać, że graf G zawiera cykl nieprzechodzący przez e.
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 24 maja 2016, o 01:13 
Użytkownik

Posty: 322
Lokalizacja: Toruń
Jeśli graf jest skierowany, to teza jest nieprawdziwa.
Jeśli graf jest nieskierowany, to dowód jest prosty.
Rozważmy dwa cykle C i D, w której kolejne krawędzie oznaczmy następująco:
C:\ c_1,c_2,\ldots,c_m,
D:\ d_1,d_2,\ldots,d_n, przy czym tak oznaczamy krawędzie, aby c_1=d_1=e. Wtedy cyklem niezawierający e jest cykl:
d_m,d_{m-1},\ldots,d_3,d_2,c_2,c_3,\ldots,c_m.
Góra
Mężczyzna Offline
PostNapisane: 24 maja 2016, o 11:07 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
To nie jest prawda. Nikt nie broni cyklom C i D się zazębiać i wtedy powyższa trasa nie jest cyklem.
Góra
Mężczyzna Offline
PostNapisane: 24 maja 2016, o 11:30 
Użytkownik

Posty: 322
Lokalizacja: Toruń
A co to przeszkadza? Jak rozumiem, wymagany jest dodatkowy warunek na cykl? Że np. nie powtarzają się wierzchołki, krawędzie, lub coś podobnego?
Góra
Mężczyzna Offline
PostNapisane: 25 maja 2016, o 00:57 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
Tak, właśnie o tyle to przeszkadza. Wiem, że cykl cyklowi nierówny, ale tutaj chodzi o drogę zamkniętą, a więc o coś, co np. na Wikipedii nazywa się "cyklem prostym".
Góra
Mężczyzna Offline
PostNapisane: 25 maja 2016, o 01:09 
Użytkownik

Posty: 322
Lokalizacja: Toruń
W takim razie wystarczy pokazać, że jeśli istnieje cykl, w którym wierzchołki się powtarzają, to istnieje cykl, w którym wierzchołki się nie powtarzają. Można to zrobić na dwa sposoby:
1) à la indukcyjnie: jeśli w cyklu powtarza się dany wierzchołek, a więc gdy częścią cyklu jest tak fragment:
\cdots \to A_0\to \mathbf{A_1}\to A_2\to\cdots A_k\to \mathbf{A_1}\to A_{k+1}\to \cdots,
to usuwamy z cyklu całą drogę A_0\to\cdots\to A_0 i zostaje nam
\cdots \to A_0\to \mathbf{A_1}\to A_{k+1}\to \cdots.
Ponieważ za każdym razem skraca nam się cykl, nie możemy takiej procedury powtarzać w nieskończoność. Zatem po skończonej liczbie kroków usuniemy wszystkie takie wystąpienia.
2) Metodą minimalną (tak tę metodę tymczasowo nazwijmy). Skoro istnieją cykle, to rozważmy ten najkrótszy. W nim nie mogę się powtarzać wierzchołki, bo moglibyśmy usunąć (jak w punkcie pierwszym) fragment cyklu, skracając jego długość, a przecież on jest najkrótszy.
Góra
Mężczyzna Offline
PostNapisane: 26 maja 2016, o 13:57 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
M Maciejewski napisał(a):
Rozważmy dwa cykle C i D, w której kolejne krawędzie oznaczmy następująco:
C:\ c_1,c_2,\ldots,c_m,
D:\ d_1,d_2,\ldots,d_n, przy czym tak oznaczamy krawędzie, aby c_1=d_1=e. Wtedy cyklem niezawierający e jest cykl:
d_m,d_{m-1},\ldots,d_3,d_2,c_2,c_3,\ldots,c_m.


A co właściwie oznacza c_1=d_1=e?

-- 27 maja 2016, 23:04 --

M Maciejewski napisał(a):
W takim razie wystarczy pokazać, że jeśli istnieje cykl, w którym wierzchołki się powtarzają, to istnieje cykl, w którym wierzchołki się nie powtarzają. Można to zrobić na dwa sposoby:
1) à la indukcyjnie: jeśli w cyklu powtarza się dany wierzchołek, a więc gdy częścią cyklu jest tak fragment:
\cdots \to A_0\to \mathbf{A_1}\to A_2\to\cdots A_k\to \mathbf{A_1}\to A_{k+1}\to \cdots,
to usuwamy z cyklu całą drogę A_0\to\cdots\to A_0 i zostaje nam
\cdots \to A_0\to \mathbf{A_1}\to A_{k+1}\to \cdots.
Ponieważ za każdym razem skraca nam się cykl, nie możemy takiej procedury powtarzać w nieskończoność. Zatem po skończonej liczbie kroków usuniemy wszystkie takie wystąpienia.


Weźmy taki graf, że
C:\ c_1,c_2,c_3
D:\ d_1,d_2,d_3,d_4
i d_1=c_1, d_3=c_2, d_4=c_3 oraz e=\left\{ c_1,c_3\right\}=\left\{ d_1,d_4\right\}, i postępujmy zgodnie z podaną procedurę. Piszemy sumę cykli:
d_4=c_3, d_3=c_2, d_2, d_1=c_1, c_2, c_3 i zaczynamy usuwać powtórki. Wycinamy drogę d_2,c_1,c_2 i zostajemy z c_3, c_2, c_3.
Procedura usuwania powtórek się skończyła, a cyklu brak.

Cytuj:
2) Metodą minimalną (tak tę metodę tymczasowo nazwijmy). Skoro istnieją cykle, to rozważmy ten najkrótszy. W nim nie mogę się powtarzać wierzchołki, bo moglibyśmy usunąć (jak w punkcie pierwszym) fragment cyklu, skracając jego długość, a przecież on jest najkrótszy.


Ta argumentacja opiera się na tym samym założeniu co w punkcie 1), tj. że skracanie cyklu zawsze prowadzi do cyklu, co - jak widać - nie jest prawdą.
Góra
Mężczyzna Offline
PostNapisane: 4 cze 2016, o 21:51 
Użytkownik

Posty: 32
Lokalizacja: W-wa
Być może ten dowód będzie prawidłowy.

Skoro cykle C i D mogę się zazębiać, to załóżmy, że mają one k wspólnych krawędzi, a więc muszą mieć także k+1 wspólnych wierzchołków (wierzchołki są incydentne do krawędzi). W związku z tym graf C \cup D - e ma \left| C\right| + \left| D\right| - k - 1 krawędzi oraz co najwyżej \left| C\right| + \left| D\right| - k - 1 wierzchołków. Ponieważ otrzymany graf ma co najmniej tyle krawędzi co wierzchołków, to musi istnieć cykl.
Góra
Mężczyzna Offline
PostNapisane: 7 cze 2016, o 20:26 
Użytkownik

Posty: 1427
Lokalizacja: Warszawa
Bardzo eleganckie rozwiązanie! :-)

Od siebie dodam ścisłe uzasadnienie ostatniego stwierdzenia. Być może strzelę z armaty, ale ja nie potrafię tego prościej wykazać.

michals95 napisał(a):
Ponieważ otrzymany graf ma co najmniej tyle krawędzi co wierzchołków, to musi istnieć cykl.


Stwierdzenie równoważne: jeśli w G nie ma cyklu, to |E(G)|<|V(G)|.

Dowód. Graf G jest lasem, a więc sumą k drzew T_i, gdzie k \ge 1. Z charakteryzacji drzew mamy teraz:

|E(G)|=\sum_{i=1}^k|E(T_i)|=\sum_{i=1}^k(|V(T_i)|-1)=\sum_{i=1}^k|V(T_i)|-k=|V(G)|-k \le |V(G)|-1<|V(G)|
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 9 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Kolorowanie gałęzi w grafie  kontouzytkownika100  0
 Ilość krawędzi w grafie na podstawie stopni wierzchołków  TrzyRazyCztery  2
 Liczba krawędzi w grafie dwudzielnym  PabloG  1
 Liczba regionów w grafie planarnym  sinus alfa  0
 Liczba dróg w grafie.  Albatross201  13
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl