szukanie zaawansowane
 [ Posty: 6 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Graf Petersena
PostNapisane: 18 gru 2018, o 17:30 
Użytkownik

Posty: 5679
Lokalizacja: Kraków
Trzy zadania:

Graf Knesera K(r, n); V= \{ podzbiory  \  r - elementowe \ zbioru  \  \{ 1, ..., n \} \} to zbiór wierzchołków. AB jest krawędzią jeśli A \cap B = \emptyset.
Udowodnić że 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.
Góra
Mężczyzna Offline
 Tytuł: Graf Petersena
PostNapisane: 18 gru 2018, o 21:22 
Użytkownik
Avatar użytkownika

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

Ukryta treść:    

mol_ksiazkowy napisał(a):
Wykazać, że ma ścieżkę Hamiltona, ale nie ma cyklu Hamiltona.

Ukryta treść:    

mol_ksiazkowy napisał(a):
Udowodnić, że graf Petersena jest grafem trójdzielnym

Ukryta treść:    
Góra
Mężczyzna Offline
 Tytuł: Graf Petersena
PostNapisane: 18 gru 2018, o 22:02 
Użytkownik

Posty: 5679
Lokalizacja: Kraków
4) Udowodnij że graf z rysunku jest izomorficzny z grafem Petersena

Obrazek
Góra
Mężczyzna Offline
PostNapisane: 18 gru 2018, o 22:24 
Użytkownik
Avatar użytkownika

Posty: 6670
Ukryta treść:    
Góra
Mężczyzna Offline
 Tytuł: Graf Petersena
PostNapisane: 3 sty 2019, o 14:50 
Użytkownik

Posty: 5679
Lokalizacja: Kraków
5) wyznaczyć indeks chromatyczny grafu Petersena
6) wykazać że może być rozłożony na 1 faktor i 2 faktor

Obrazek
Góra
Mężczyzna Offline
PostNapisane: 14 sty 2019, o 15:40 
Użytkownik
Avatar użytkownika

Posty: 6670
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:    
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 6 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Graf petersena  Ceplusplusik  1
 Graf mający zbiór wierzchołków  Cabalerio  3
 Czy istnieje graf - zadanie 2  max123321  1
 3 zadania: szachownica, graf, rekurencja  jraven  3
 Graf doskonaly.  RobiMethod  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl