Witam, czy ktoś mógłby mi pomóc z zadaniami z matematyki dyskretnej? Chodzi o zadania z grafami
W jednym z zadań muszę narysować graf o ciągu stopni : \(\displaystyle{ (3,3,3,2,1)}\)
W drugim muszę rozważyć które z następujących ciągów są grafowe?
\(\displaystyle{ (6, 6, 5, 5, 2, 2, 2, 2).\\
(6, 6, 5, 5, 3, 3, 3, 3).}\)
Dla ciągów, które są grafowe, narysuj odpowiednie grafy (proste).
grafy, ciągi stopni
-
Samiiiidare
- Użytkownik
- Posty: 1
- Rejestracja: 14 sty 2017, o 15:27
- Płeć: Kobieta
- Lokalizacja: Gdynia
grafy, ciągi stopni
Ostatnio zmieniony 1 lip 2017, o 20:03 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Re: grafy, ciągi stopni
Można zastosować to ogólne twierdzenie:
Tutaj masz ogólny algorytm:
Inaczej:
Dla ciągu stopni \(\displaystyle{ (6, 6, 5, 5, 2, 2, 2, 2)}\) graf prosty nie istnieje. Weźmy dowolny wierzchołek stopnia \(\displaystyle{ 6}\). Musi być on połączony z przynajmniej trzema wierzchołkami stopnia \(\displaystyle{ 2}\). To znaczy, że istnieją co najmniej dwa wierzchołki stopnia \(\displaystyle{ 2}\) połączone z oboma wierzchołkami stopnia \(\displaystyle{ 6}\). Połączmy je i wyrzućmy z grafu, mamy ciąg stopni \(\displaystyle{ (4, 4, 5, 5, 2, 2)}\). Wtedy każdy z wierzchołków stopnia \(\displaystyle{ 5}\) musi być połączony ze wszystkimi pozostałymi wierzchołkami. Połączmy je i wyrzućmy z grafu. Zostaje ciąg stopni: \(\displaystyle{ (2, 2)}\), nie jest on grafowy.
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theoremTutaj masz ogólny algorytm:
Kod: Zaznacz cały
http://www.deltami.edu.pl/temat/informatyka/algorytmy/2011/11/01/Odtwarzanie_grafu/Inaczej:
Dla ciągu stopni \(\displaystyle{ (6, 6, 5, 5, 2, 2, 2, 2)}\) graf prosty nie istnieje. Weźmy dowolny wierzchołek stopnia \(\displaystyle{ 6}\). Musi być on połączony z przynajmniej trzema wierzchołkami stopnia \(\displaystyle{ 2}\). To znaczy, że istnieją co najmniej dwa wierzchołki stopnia \(\displaystyle{ 2}\) połączone z oboma wierzchołkami stopnia \(\displaystyle{ 6}\). Połączmy je i wyrzućmy z grafu, mamy ciąg stopni \(\displaystyle{ (4, 4, 5, 5, 2, 2)}\). Wtedy każdy z wierzchołków stopnia \(\displaystyle{ 5}\) musi być połączony ze wszystkimi pozostałymi wierzchołkami. Połączmy je i wyrzućmy z grafu. Zostaje ciąg stopni: \(\displaystyle{ (2, 2)}\), nie jest on grafowy.