Problém s realizací grafu - Graph realization problem

The problém realizace grafu je rozhodovací problém v teorie grafů. Vzhledem k konečné posloupnosti ${ displaystyle (d_ {1}, tečky, d_ {n})}$ přirozených čísel, problém se ptá, zda je označen jednoduchý graf takhle ${ displaystyle (d_ {1}, tečky, d_ {n})}$ je sekvence stupňů tohoto grafu.

Řešení

Problém lze vyřešit v polynomiální čas. Jeden způsob, jak to ukázat, používá Algoritmus Havel – Hakimi konstrukce speciálního řešení s využitím a rekurzivní algoritmus.^[1][2] Alternativně podle charakterizace dané Erdős – Gallaiova věta, problém lze vyřešit testováním platnosti ${ displaystyle n}$ nerovnosti.^[3]

Jiné notace

Problém lze také konstatovat z hlediska symetrické matice nul a jedniček. Spojení lze vidět, pokud si člověk uvědomí, že každý graf má matice sousedství kde součty sloupců a součty řádků odpovídají ${ displaystyle (d_ {1}, ldots, d_ {n})}$. Problém pak někdy označuje symetrické 0-1-matice pro dané součty řádků.

Související problémy

Podobné problémy popisují stupně z jednoduché bipartitní grafy nebo stupně z jednoduché směrované grafy. Prvním problémem je tzv bipartitní realizační problém. Druhý je známý jako problém realizace digrafu.

Ukázalo se, že problém konstrukce řešení problému realizace grafu s dodatečným omezením, že každé takové řešení přichází se stejnou pravděpodobností, má schéma aproximace v polynomiálním čase pro posloupnosti stupňů pravidelné grafy Cooper, Martin a Greenhill.^[4] Obecný problém stále není vyřešen.

Reference