A gráfok esetében nincs más megoldás erre a feladatra?

A feladat jellegétől függ, hogy hányféle gráf rajzolható fel. Ha jól emlékszem, akkor az idei érettségiben is volt olyan feladat, hogy a megadottak szerint kellett rajzolni egy gráfot, és hogy az adott pontnak mennyi volt a fokszáma, és rajzolástól függően több megoldás volt.

Amit a tanár lényegében mondott, az a Hakimi-algoritmus; mindig válasszuk ki a legnagyobb fokszámút, és azt a legnagyobb fokszámúakkal kössük össze. Ha ez megvan, akkor válasszuk ki a következő legnagyobb fokszámút, és ismételjük addig, amíg el nem fogynak a fokszámok. Maga az algoritmus biztosan megoldást ad a feladatra, de nem garantálja, hogy csak egyféle megoldás van (ez elsősorban abból adódik, hogy ha több legnagyobb fokszámú van, akkor nekünk kell döntenünk, hogy melyikkel számolunk előbb, és ebből eredhetnek különböző rajzolatok), de ha csak egy megoldás van, azt ez az algoritmus biztosan kiadja.

[link]