Graf Petersena
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Graf Petersena
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.
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.
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Graf Petersena
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ść:
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Graf Petersena
5) wyznaczyć indeks chromatyczny grafu Petersena
6) wykazać że może być rozłożony na \(\displaystyle{ 1}\) faktor i \(\displaystyle{ 2}\) faktor
6) wykazać że może być rozłożony na \(\displaystyle{ 1}\) faktor i \(\displaystyle{ 2}\) faktor
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: Graf Petersena
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)
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:
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Graf Petersena
Czy graf Petersena jest krytyczny ?
Graf krytyczny to taki, w którym po usunięciu dowolnego wierzchołka zmniejsza się jego liczba chromatyczna.
Graf krytyczny to taki, w którym po usunięciu dowolnego wierzchołka zmniejsza się jego liczba chromatyczna.
- VirtualUser
- Użytkownik
- Posty: 443
- Rejestracja: 2 wrz 2017, o 11:13
- Płeć: Mężczyzna
- Podziękował: 113 razy
- Pomógł: 15 razy
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Re: Graf Petersena
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 ?
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: Graf Petersena
3 oraz 3mol_ksiazkowy pisze: ↑14 gru 2020, o 17:11 Wyznaczyć spójność krawędziową i wierzchołkową grafu Petersena
4mol_ksiazkowy pisze: ↑21 sty 2022, o 19:15 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 ?
PS. Wieczorem (lub wcześniej, jeśli znajdę trochę czasu) dopiszę uzasadnienia powyższych wyników.
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Re: Graf Petersena
Wyznaczyć grupę automorfizmów grafu Petersena ; wykorzystać zę jest dopełnieniem grafu krawędziowego \(\displaystyle{ K_5}\)
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Graf Petersena
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}}\)...
\(\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}}\)...
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
- arek1357
- Użytkownik
- Posty: 5747
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 526 razy
Re: Graf Petersena
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...
\(\displaystyle{ 3,3,1,1,1,1}\)
A więc nietrudno wskazać izomorfizm między tymi podgrafami...
- Załączniki
-
- plik
- peterson3.jpg (30.11 KiB) Przejrzano 506 razy