Forum matematyczne: miliony postów, setki tysięcy tematów, dziesiątki tysięcy użytkowników - pomożemy rozwiązać każde zadanie z matematyki https://matematyka.pl/
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 Petersena
: 18 gru 2018, o 21:22
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ść:
K(2,5) zawiera \(\displaystyle{ {5 \choose 2}=10}\) wierzchołków. Są to:\(\displaystyle{ (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}\)
Wystarczy poetykietować tymi wierzchołkami graf Petersena aby wykazać izomorfizm
a.jpg (17.49 KiB) Przejrzano 2842 razy
mol_ksiazkowy pisze:Wykazać, że ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.
Ukryta treść:
Cykl Hamiltona maja grafy dwudzielne, czyli takie których wierzchołki można pokolorować dwoma barwami i żadne dwa wierzchołki o tej samej barwie nie mają wspólnej krawędzi.
Kolorowanie wierzchołków (grafika pokazuje dwa jego etapy):
a2.jpg (29.37 KiB) Przejrzano 2843 razy
Jak widać ostatnich dwóch niebieskich wierzchołków z prawego grafu nie można zabarwić tak aby nie miał wspólnej krawędzi z wierzchołkiem o tej samej barwie (ponadto są już żółte wierzchołki o wspólnej krawędzi) . Graf nie jest dwudzielny, więc nie ma cyklu Hamiltona.
Przykładowa ścieżka Hamiltona:
a1.png (21.23 KiB) Przejrzano 2841 razy
mol_ksiazkowy pisze:Udowodnić, że graf Petersena jest grafem trójdzielnym
Ukryta treść:
Kolejne etapy kolorowania trzema barwami:
Graf Petersena
: 18 gru 2018, o 22:02
autor: mol_ksiazkowy
4) Udowodnij że graf z rysunku jest izomorficzny z grafem Petersena
Re: Graf Petersena
: 18 gru 2018, o 22:24
autor: kerajs
Ukryta treść:
1.jpg (18.46 KiB) Przejrzano 2786 razy
Graf Petersena
: 3 sty 2019, o 14:50
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
200px-Petersen_graphsvg.png (6.79 KiB) Przejrzano 1018 razy
Re: Graf Petersena
: 14 sty 2019, o 15:40
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:
Graf Petersena
: 5 sie 2019, o 11:08
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.
Re: Graf Petersena
: 5 sie 2019, o 22:29
autor: VirtualUser
A spróbuję...
Ukryta treść:
Graf petersena ma liczbę chromatyczną \(\displaystyle{ 3}\). Spróbujemy pomalować go na \(\displaystyle{ 2}\) kolory po usunięciu wierzchołka z zewnętrznego pierścienia.
Bez straty ogólności: \(\displaystyle{ 1}\) malujemy na czerwono.
W takim razie \(\displaystyle{ 9}\) i \(\displaystyle{ 2}\) na niebiesko
Wnet \(\displaystyle{ 8}\) i \(\displaystyle{ 7}\) na czerwono - sprzeczność, czyli potrzebujemy \(\displaystyle{ \ge 3}\) kolory. Stąd liczba chromatyczna nie zmalała stąd graf petersena nie jest krytyczny.
Re: Graf Petersena
: 14 gru 2020, o 17:11
autor: mol_ksiazkowy
Wyznaczyć spójność krawędziową i wierzchołkową grafu Petersena
Re: Graf Petersena
: 21 sty 2022, o 19:15
autor: mol_ksiazkowy
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 ?
Re: Graf Petersena
: 25 sty 2022, o 08:28
autor: kerajs
mol_ksiazkowy pisze: ↑14 gru 2020, o 17:11 Wyznaczyć spójność krawędziową i wierzchołkową grafu Petersena
3 oraz 3
mol_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 ?
4
PS. Wieczorem (lub wcześniej, jeśli znajdę trochę czasu) dopiszę uzasadnienia powyższych wyników.
Re: Graf Petersena
: 28 lis 2022, o 19:25
autor: mol_ksiazkowy
Wyznaczyć grupę automorfizmów grafu Petersena ; wykorzystać zę jest dopełnieniem grafu krawędziowego \(\displaystyle{ K_5}\)
Re: Graf Petersena
: 29 lis 2022, o 23:21
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:
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}}\)...
Re: Graf Petersena
: 20 gru 2022, o 19:53
autor: mol_ksiazkowy
Wskazać rozkład grafu Petersena na trzy izomorficzne podgrafy .
Re: Graf Petersena
: 20 gru 2022, o 22:33
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...
Wyznaczyć spójność krawędziową i wierzchołkową grafu Petersena