Jak sprawdzić czy da się narysować graf?

too_hrd · Post autor: **too_hrd** » 15 wrz 2012, o 18:23

Witam,
Jak wyżej, jakie musi spełniać warunki gra np. 1 2 2 3 4, żeby można go było narysować?

justynian · Post autor: **justynian** » 15 wrz 2012, o 18:36

algorytm Havla-Hakimiego

too_hrd · Post autor: **too_hrd** » 15 wrz 2012, o 19:16

justynian pisze:algorytm Havla-Hakimiego

Ok, ale pamiętam że były jakieś założenia. Np. Suma wszystkich krawędzi musi być parzysta itp. Właśnie nigdzie nawet w wikipedii nie mogę znaleźć tego.

justynian · Post autor: **justynian** » 15 wrz 2012, o 19:47

To w ogóle warunek konieczny aby suma stopni wierzchołków była parzysta. Następnie łączymy jakiś wierzchołek z odpowiednią liczbą innych usuwamy je i tak aż dostaniem wierzchołki o których już wiemy czy budują graf czy nie.

too_hrd · Post autor: **too_hrd** » 15 wrz 2012, o 19:59

A istnieje możliwość sprawdzenia tego bez konieczności stosowania algorytmu? Co należy właśnie uwzględnić oprócz parzystości?

justynian · Post autor: **justynian** » 15 wrz 2012, o 20:49

Tak, kryterium Erdosa do znalezienia tutaj ... nie_grafu/ .