Graf Petersena

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Graf Petersena

Post autor: mol_ksiazkowy »

Trzy zadania:

Graf Knesera \(\displaystyle{ K(r, n)}\); \(\displaystyle{ V= \{ podzbiory \ r - elementowe \ zbioru \ \{ 1, ..., n \} \}}\) to zbiór wierzchołków. \(\displaystyle{ AB}\) jest krawędzią jeśli \(\displaystyle{ A \cap B = \emptyset}\).
Udowodnić że \(\displaystyle{ K(2,5)}\) jest izomorficzny z grafem Petersena

Udowodnić, że graf Petersena jest grafem trójdzielnym

Wykazać, że ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Graf Petersena

Post autor: kerajs »

mol_ksiazkowy pisze:Graf Knesera \(\displaystyle{ K(r, n)}\); \(\displaystyle{ V= \{ podzbiory \ r - elementowe \ zbioru \ \{ 1, ..., n \} \}}\) to zbiór wierzchołków. \(\displaystyle{ AB}\) jest krawędzią jeśli \(\displaystyle{ A \cap B = \emptyset}\).
Udowodnić że \(\displaystyle{ K(2,5)}\) jest izomorficzny z grafem Petersena
Ukryta treść:    
mol_ksiazkowy pisze:Wykazać, że ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
Ukryta treść:    
mol_ksiazkowy pisze:Udowodnić, że graf Petersena jest grafem trójdzielnym
Ukryta treść:    
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Graf Petersena

Post autor: mol_ksiazkowy »

4) Udowodnij że graf z rysunku jest izomorficzny z grafem Petersena

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Graf Petersena

Post autor: kerajs »

Ukryta treść:    
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Graf Petersena

Post autor: mol_ksiazkowy »

5) wyznaczyć indeks chromatyczny grafu Petersena
6) wykazać że może być rozłożony na \(\displaystyle{ 1}\) faktor i \(\displaystyle{ 2}\) faktor
AU
AU
200px-Petersen_graphsvg.png (6.79 KiB) Przejrzano 960 razy
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Graf Petersena

Post autor: kerajs »

Ad 5)
Ten graf jest najmniejszym żmirłaczem, więc jak i pozostałe snarki ma indeks chromatyczny równy 4 (przykładowe pokolorowanie na rys. 5).

Ad 6)
1-faktor to skojarzenie doskonałe (kolor czerwony na rys. 6)
2-faktor to cykle zawierające wszystkie wierzchołki grafu Petersena (kolory zielone na rys. 6)
Rys:    
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Graf Petersena

Post autor: mol_ksiazkowy »

Czy graf Petersena jest krytyczny ?

Graf krytyczny to taki, w którym po usunięciu dowolnego wierzchołka zmniejsza się jego liczba chromatyczna.
Awatar użytkownika
VirtualUser
Użytkownik
Użytkownik
Posty: 443
Rejestracja: 2 wrz 2017, o 11:13
Płeć: Mężczyzna
Podziękował: 113 razy
Pomógł: 15 razy

Re: Graf Petersena

Post autor: VirtualUser »

A spróbuję...
Ukryta treść:    
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Re: Graf Petersena

Post autor: mol_ksiazkowy »

:arrow: Wyznaczyć spójność krawędziową i wierzchołkową grafu Petersena
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Re: Graf Petersena

Post autor: mol_ksiazkowy »

:arrow: Antyklika to zbiór wierzchołków, z których żadne nie łączy krawędź. Ile jest równa liczność największej antykliki w grafie Petersena ?
Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 8570
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 306 razy
Pomógł: 3347 razy

Re: Graf Petersena

Post autor: kerajs »

mol_ksiazkowy pisze: 14 gru 2020, o 17:11 :arrow: Wyznaczyć spójność krawędziową i wierzchołkową grafu Petersena
3 oraz 3
mol_ksiazkowy pisze: 21 sty 2022, o 19:15 :arrow: Antyklika to zbiór wierzchołków, z których żadne nie łączy krawędź. Ile jest równa liczność największej antykliki w grafie Petersena ?
4

PS. Wieczorem (lub wcześniej, jeśli znajdę trochę czasu) dopiszę uzasadnienia powyższych wyników.
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Re: Graf Petersena

Post autor: mol_ksiazkowy »

Wyznaczyć grupę automorfizmów grafu Petersena ; wykorzystać zę jest dopełnieniem grafu krawędziowego \(\displaystyle{ K_5}\)
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Graf Petersena

Post autor: arek1357 »

Jest tu tego typu sprawa, że jeżeli weźmiemy zbiór:

\(\displaystyle{ Z= \left\{ 1,2,3,4,5\right\} }\)

Mamy:

\(\displaystyle{ {5 \choose 2} =10}\) - par z tego zbioru, np:

\(\displaystyle{ P=\left\{ \left\{ 1,2\right\} , \left\{ 1,3\right\} , \left\{ 4,5\right\} ,...\right\} }\)

Jak z tych par utworzymy graf w ten sposób, że łączymy dwa punkty z \(\displaystyle{ P }\) jeżeli ich przecięcie jest zbiorem pustym, otrzymamy dokładnie graf Petersena...

I teraz każdy automorfizm zbioru Z wyznacza automorfizm zbioru \(\displaystyle{ P}\) tak, że krawędź przechodzi na krawędź...

Automorfizmów zbioru \(\displaystyle{ Z}\) jest dokładnie \(\displaystyle{ 5!=120}\)

Czyli jest to grupa:

\(\displaystyle{ S_{5}}\)...
Awatar użytkownika
mol_ksiazkowy
Użytkownik
Użytkownik
Posty: 11263
Rejestracja: 9 maja 2006, o 12:35
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 3140 razy
Pomógł: 746 razy

Re: Graf Petersena

Post autor: mol_ksiazkowy »

Wskazać rozkład grafu Petersena na trzy izomorficzne podgrafy .
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Graf Petersena

Post autor: arek1357 »

Trzy podgrafy każdy ma tego samego stopnia wierzchołki:

\(\displaystyle{ 3,3,1,1,1,1}\)

A więc nietrudno wskazać izomorfizm między tymi podgrafami...
Załączniki
plik
plik
peterson3.jpg (30.11 KiB) Przejrzano 485 razy
ODPOWIEDZ