grafy
lola456: Witam, mam zadanie z teorii grafów a nie mogę nigdzie znaleźć sposobu jak rozwiązać podany
problem:
Rozstrzygnij, czy istnieją grafy o następujących ciągach wierzchołków:
a) (3, 3, 3, 3, 3, 2)
b) (7, 7, 4, 4, 3, 3, 2, 2)
Jak się zabrać za rozwiązywanie takich zadań?
Bardzo proszę o pomoc
13 gru 21:56
Adamm: suma wierzchołków w grafie jest liczbą parzystą
13 gru 22:04
lola456: Czyli w obu przypadkach te grafy nie istnieją?
13 gru 22:05
lola456: A jeżeli mam (5, 5, 4, 4, 2, 2) to suma jest parzysta i wystarczy napisać że taki graf istnieje
czy coś trzeba sprawdzać?
13 gru 22:06
13 gru 22:07
lola456: Znalazłam właśnie te materiały, natomiast czy mogłabym poprosić o rozwiązanie choć jednego
przykładu tak, żebym lepiej zrozumiała?
13 gru 22:08
Adamm: na oba pytania odpowiedź negatywna
13 gru 22:09
a7: a) 3+3+3+3+3+2 jest liczbą nieparzystą więc taki graf nie istnieje
13 gru 22:31
a7: b) suma stopni jest parzysta (ale to nie wystarczy) teraz trzeba skorzystać algorytmu
zachłannego z linku 2
13 gru 22:41
jc:
72
13 gru 22:42
lola456: Rozumiem
dziękuję bardzo wszystkim za pomoc
14 gru 18:26