Gráfok, segitesz?

Az egyik pontból rajzolsz 4 élt.

És ezután próbálgatsz.

Van egy általános eljárás, ami minden esetben ad egy eredményt (ha pedig csak egy megoldás van, akkor azt az egyet), ez a Hakimi-algoritmus. Középiskolában nem szokták tanítani, de nem árt, ha tudod.

A lényeg:

1. lépés: kiválasztod a legnagyobb fokszámú csúcsot (ha több van belőlük, akkor tetszőlegesen az egyiket).

2. lépés: a kiválasztott csúcsot annak fokszámának megfelelően összekötöd csúcsokkal. Nagyon fontos, hogy a lehető legnagyobb fokszámú csúcsokkal kösd össze.

3. lépés: a behúzások miatt mindegyik, összekötésben részt vevő csúcs fokszáma gyakorlatilag 1-gyel csökkent (a kiválasztott csúcs fokszáma pedig 0 lett, mivel ő már nem kap élt). Innentől vissza az 1. lépésre. Ezt addig csináljuk, amíg nem kapjuk meg a gráfot (vagy eladakad az algoritmus, ilyenkor nem létezik a fokszámokkal gráf, de ezt külön kell bizonyítani).

Esetünkben:

4, 3, 3, 2, 2, a 4-es a legnagyobb, ezért a 4 legnagyobb fokszámú csúccsal összekötjük (most más lehetőségünk amúgy sincs). A behúzás után ezek a fokszámok:

0, 2, 2, 1, 1, a szabályt követve kiválasztom az első kettest, ezt összekötöm a másik 2-essel és az egyik 1-essel (mindegy, hogy melyikkel), ekkor:

0, 0, 1, 1, 0, végül pedig a két egyest összekötjük:

0, 0, 0, 0, 0, itt megáll az algoritmus, a megfelelő gráfot pedig megtaláltuk.