szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 31 lip 2015, o 13:07 
Użytkownik

Posty: 394
Lokalizacja: Warszawa
Natknąłem się na takie pytanie,dla jakich r istnieje r-regularny graf o spójności jeden.

Widać,że w tym grafie musi istnieć więc wierzchołek rozdzielający. Tylko pytanie czy istnieje dla każdego r? Musiałbym za każdym razem stworzyć 2 grafy regularne i łączyć je za pomocą tego właśnie wierzchołka,nie zapominając ,że w chwili łączenia regularność tych 2 grafów również się zmienia. Jakieś pomysły?
Góra
Mężczyzna Offline
PostNapisane: 2 sie 2015, o 11:41 
Gość Specjalny

Posty: 3051
Lokalizacja: Gołąb
Napiszę tyle. Dla każdego 2|r i r>2 taki graf istnieje. Dla pozostałych prawdopodobnie nie. Jak znajdę poprawny dowód to go napiszę :D

-- 2 sie 2015, o 13:45 --

Nikt mnie nie wyręczył, ani nie ubiegł, zatem napiszę rozwiązanie tego zadania.
Rozpoczniemy od pokazania, że jeżeli taki graf istnieje to 2|r.
Załóżmy, że istnieje graf r-regularny G, który ma wierzchołek rozcinający v. Zauważmy, że graf H=G \setminus v jest niespójny. Oznaczmy jego spójne składowe przez S_{1},S_{2},\dots , S_{k}, k>1. Niech liczby n_{1}, n_{2}, \dots , n_{k} oznaczają odpowiednio liczby wierzchołków w składowych odpowiednio S_{1},S_{2},\dots , S_{k}, zaś liczby p_{1}, p_{2}, \dots ,p_{k} niech oznaczają liczby wierzchołków zawartych odpowiednio w S_{1},S_{2},\dots , S_{k}, które sąsiadują w grafie G z wierzchołkiem v.
Rozważając każdą ze składowych S_{1},S_{2},\dots , S_{k} na mocy lematu o uściskach dłoni, że dla każdego i =1,2,\dots , k zachodzi podzielność:
2|p_{i}\left(r-1\right)+\left(n_{i}-p_{i}\right)r=n_{1}r-p_{1}
"Sumując" te k podzielności i uwzględniając dodatkowo, że \sum_{i=1}^{k}n_{i}=n=\left|G\right| oraz \sum_{i=1}^{k}p_{i}=r otrzymujemy:
2|nr-r=\left(n-1\right)r.
Tymczasem, korzystając z lematu o uściskach dłoni dla grafu G mamy 2|nr co w konsekwencji z uzyskaną wyżej podzielnością dowodzi że musi być 2|r. \square

Mamy zatem warunek konieczny 2|r. Nie jest on jednak wystarczający. Weźmy r=2. Oczywiście spójny graf dwu-regularny musi być cyklem. Jednak żaden cykl nie posiada wierzchołka rozcinającego.

Pozostał więc tylko przypadek 2|r i r>2. Pokażemy, że dla dowolnego takiego r graf o własności z zadania istnieje.
Oto konstrukcja takiego grafu.
Bierzemy \frac{r}{2} grafów pełnych i niech każdy z nich ma r+1 wierzchołków. Z każdego z nich wyrzucamy jedną krawędź. Końce tej krawędzi łączymy z dołożonym nowym wierzchołkiem v. W ten sposób otrzymujemy graf G.
Pozostaje pokazać, że spełnia on warunki zadania.
Istotnie, zauważmy, że ten graf jest r-regularny. Aby się o tym przekonać sprawdzamy 3 rodzaje wierzchołków:
1. Wierzchołki w grafach pełnych które nie są końcami wyrzuconych krawędzi. Oczywiście ich stopień jest taki sam jak w grafie pełnym o r+1 wierzchołkach i wynosi r
2. Wierzchołki w grafach pełnych które są końcami wyrzuconej krawędzi. Ich stopnień wynosi również r, bo taki był w grafie pełnym, odrzuciliśmy jedną krawędź, ale za to połączyliśmy te wierzchołki z v
3. Wreszcie wierzchołek v również ma stopień r, ponieważ sąsiaduje z 2 wierzchołkami w każdym z grafów pełnych, a tych jest \frac{r}{2}
Dodatkowo, jeżeli \frac{r}{2}>1 \Leftrightarrow r>2 to wierzchołek v jest wierzchołkiem rozcinającym takiego grafu.
Kończy to rozwiązanie tego jakże pięknego zadania.
Pozdrawiam :D
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Automorfizmy grafu  dusiek  3
 Spójność grafu - zadanie 5  alto de aitana  3
 Kolorowanie grafu - zadanie 2  bartm  2
 wierzchołki nie rozspójniające grafu  kolegasafeta  1
 Średnica grafu samodopełniającego  kubek1  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl