Natknąłem się na takie pytanie,dla jakich \(\displaystyle{ r}\) istnieje \(\displaystyle{ 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 \(\displaystyle{ 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?
Spójność grafu regularnego
-
bakala12
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Spójność grafu regularnego
Napiszę tyle. Dla każdego \(\displaystyle{ 2|r}\) i \(\displaystyle{ r>2}\) taki graf istnieje. Dla pozostałych prawdopodobnie nie. Jak znajdę poprawny dowód to go napiszę
-- 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 \(\displaystyle{ 2|r}\).
Załóżmy, że istnieje graf \(\displaystyle{ r}\)-regularny \(\displaystyle{ G}\), który ma wierzchołek rozcinający \(\displaystyle{ v}\). Zauważmy, że graf \(\displaystyle{ H=G \setminus v}\) jest niespójny. Oznaczmy jego spójne składowe przez \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\), \(\displaystyle{ k>1}\). Niech liczby \(\displaystyle{ n_{1}, n_{2}, \dots , n_{k}}\) oznaczają odpowiednio liczby wierzchołków w składowych odpowiednio \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\), zaś liczby \(\displaystyle{ p_{1}, p_{2}, \dots ,p_{k}}\) niech oznaczają liczby wierzchołków zawartych odpowiednio w \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\), które sąsiadują w grafie \(\displaystyle{ G}\) z wierzchołkiem \(\displaystyle{ v}\).
Rozważając każdą ze składowych \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\) na mocy lematu o uściskach dłoni, że dla każdego \(\displaystyle{ i =1,2,\dots , k}\) zachodzi podzielność:
\(\displaystyle{ 2|p_{i}\left(r-1\right)+\left(n_{i}-p_{i}\right)r=n_{1}r-p_{1}}\)
"Sumując" te \(\displaystyle{ k}\) podzielności i uwzględniając dodatkowo, że \(\displaystyle{ \sum_{i=1}^{k}n_{i}=n=\left|G\right|}\) oraz \(\displaystyle{ \sum_{i=1}^{k}p_{i}=r}\) otrzymujemy:
\(\displaystyle{ 2|nr-r=\left(n-1\right)r}\).
Tymczasem, korzystając z lematu o uściskach dłoni dla grafu \(\displaystyle{ G}\) mamy \(\displaystyle{ 2|nr}\) co w konsekwencji z uzyskaną wyżej podzielnością dowodzi że musi być \(\displaystyle{ 2|r}\). \(\displaystyle{ \square}\)
Mamy zatem warunek konieczny \(\displaystyle{ 2|r}\). Nie jest on jednak wystarczający. Weźmy \(\displaystyle{ 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 \(\displaystyle{ 2|r}\) i \(\displaystyle{ r>2}\). Pokażemy, że dla dowolnego takiego \(\displaystyle{ r}\) graf o własności z zadania istnieje.
Oto konstrukcja takiego grafu.
Bierzemy \(\displaystyle{ \frac{r}{2}}\) grafów pełnych i niech każdy z nich ma \(\displaystyle{ 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 \(\displaystyle{ v}\). W ten sposób otrzymujemy graf \(\displaystyle{ G}\).
Pozostaje pokazać, że spełnia on warunki zadania.
Istotnie, zauważmy, że ten graf jest \(\displaystyle{ r}\)-regularny. Aby się o tym przekonać sprawdzamy \(\displaystyle{ 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 \(\displaystyle{ r+1}\) wierzchołkach i wynosi \(\displaystyle{ r}\)
2. Wierzchołki w grafach pełnych które są końcami wyrzuconej krawędzi. Ich stopnień wynosi również \(\displaystyle{ r}\), bo taki był w grafie pełnym, odrzuciliśmy jedną krawędź, ale za to połączyliśmy te wierzchołki z \(\displaystyle{ v}\)
3. Wreszcie wierzchołek \(\displaystyle{ v}\) również ma stopień \(\displaystyle{ r}\), ponieważ sąsiaduje z 2 wierzchołkami w każdym z grafów pełnych, a tych jest \(\displaystyle{ \frac{r}{2}}\)
Dodatkowo, jeżeli \(\displaystyle{ \frac{r}{2}>1 \Leftrightarrow r>2}\) to wierzchołek \(\displaystyle{ v}\) jest wierzchołkiem rozcinającym takiego grafu.
Kończy to rozwiązanie tego jakże pięknego zadania.
Pozdrawiam
-- 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 \(\displaystyle{ 2|r}\).
Załóżmy, że istnieje graf \(\displaystyle{ r}\)-regularny \(\displaystyle{ G}\), który ma wierzchołek rozcinający \(\displaystyle{ v}\). Zauważmy, że graf \(\displaystyle{ H=G \setminus v}\) jest niespójny. Oznaczmy jego spójne składowe przez \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\), \(\displaystyle{ k>1}\). Niech liczby \(\displaystyle{ n_{1}, n_{2}, \dots , n_{k}}\) oznaczają odpowiednio liczby wierzchołków w składowych odpowiednio \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\), zaś liczby \(\displaystyle{ p_{1}, p_{2}, \dots ,p_{k}}\) niech oznaczają liczby wierzchołków zawartych odpowiednio w \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\), które sąsiadują w grafie \(\displaystyle{ G}\) z wierzchołkiem \(\displaystyle{ v}\).
Rozważając każdą ze składowych \(\displaystyle{ S_{1},S_{2},\dots , S_{k}}\) na mocy lematu o uściskach dłoni, że dla każdego \(\displaystyle{ i =1,2,\dots , k}\) zachodzi podzielność:
\(\displaystyle{ 2|p_{i}\left(r-1\right)+\left(n_{i}-p_{i}\right)r=n_{1}r-p_{1}}\)
"Sumując" te \(\displaystyle{ k}\) podzielności i uwzględniając dodatkowo, że \(\displaystyle{ \sum_{i=1}^{k}n_{i}=n=\left|G\right|}\) oraz \(\displaystyle{ \sum_{i=1}^{k}p_{i}=r}\) otrzymujemy:
\(\displaystyle{ 2|nr-r=\left(n-1\right)r}\).
Tymczasem, korzystając z lematu o uściskach dłoni dla grafu \(\displaystyle{ G}\) mamy \(\displaystyle{ 2|nr}\) co w konsekwencji z uzyskaną wyżej podzielnością dowodzi że musi być \(\displaystyle{ 2|r}\). \(\displaystyle{ \square}\)
Mamy zatem warunek konieczny \(\displaystyle{ 2|r}\). Nie jest on jednak wystarczający. Weźmy \(\displaystyle{ 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 \(\displaystyle{ 2|r}\) i \(\displaystyle{ r>2}\). Pokażemy, że dla dowolnego takiego \(\displaystyle{ r}\) graf o własności z zadania istnieje.
Oto konstrukcja takiego grafu.
Bierzemy \(\displaystyle{ \frac{r}{2}}\) grafów pełnych i niech każdy z nich ma \(\displaystyle{ 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 \(\displaystyle{ v}\). W ten sposób otrzymujemy graf \(\displaystyle{ G}\).
Pozostaje pokazać, że spełnia on warunki zadania.
Istotnie, zauważmy, że ten graf jest \(\displaystyle{ r}\)-regularny. Aby się o tym przekonać sprawdzamy \(\displaystyle{ 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 \(\displaystyle{ r+1}\) wierzchołkach i wynosi \(\displaystyle{ r}\)
2. Wierzchołki w grafach pełnych które są końcami wyrzuconej krawędzi. Ich stopnień wynosi również \(\displaystyle{ r}\), bo taki był w grafie pełnym, odrzuciliśmy jedną krawędź, ale za to połączyliśmy te wierzchołki z \(\displaystyle{ v}\)
3. Wreszcie wierzchołek \(\displaystyle{ v}\) również ma stopień \(\displaystyle{ r}\), ponieważ sąsiaduje z 2 wierzchołkami w każdym z grafów pełnych, a tych jest \(\displaystyle{ \frac{r}{2}}\)
Dodatkowo, jeżeli \(\displaystyle{ \frac{r}{2}>1 \Leftrightarrow r>2}\) to wierzchołek \(\displaystyle{ v}\) jest wierzchołkiem rozcinającym takiego grafu.
Kończy to rozwiązanie tego jakże pięknego zadania.
Pozdrawiam