szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 14 sty 2017, o 16:02 
Użytkownik

Posty: 1
Lokalizacja: Gdynia
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 : (3,3,3,2,1)

W drugim muszę rozważyć które z następujących ciągów są grafowe?
(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).
Góra
Mężczyzna Offline
PostNapisane: 1 lip 2017, o 18:55 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Można zastosować to ogólne twierdzenie:
https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Gallai_theorem

Tutaj masz ogólny algorytm: http://www.deltami.edu.pl/temat/informatyka/algorytmy/2011/11/01/Odtwarzanie_grafu/

Inaczej:
Dla ciągu stopni (6, 6, 5, 5, 2, 2, 2, 2) graf prosty nie istnieje. Weźmy dowolny wierzchołek stopnia 6. Musi być on połączony z przynajmniej trzema wierzchołkami stopnia 2. To znaczy, że istnieją co najmniej dwa wierzchołki stopnia 2 połączone z oboma wierzchołkami stopnia 6. Połączmy je i wyrzućmy z grafu, mamy ciąg stopni (4, 4, 5, 5, 2, 2). Wtedy każdy z wierzchołków stopnia 5 musi być połączony ze wszystkimi pozostałymi wierzchołkami. Połączmy je i wyrzućmy z grafu. Zostaje ciąg stopni: (2, 2), nie jest on grafowy.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ciągi słabo rosnące  Lukassz  2
 Drzewa i grafy dwuspójne  rubik1990  1
 Grafy z liczbami pierwszymi oraz funkcje  GypsyHatter  3
 Ciągi z 0,1,2.  myszka9  1
 4 zadania - grafy.  anitalochowicz  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl