Grafrekonstruksjon

Grafrekonstruksjon er et tema i grafteori som undersøker hvor mye av en graf som kan bestemmes ut fra en samling undergrafer som oppstår ved å fjerne enkelte noder eller kanter. Den mest studerte varianten er rekonstruksjon fra vertex-deleted subgrafer. For en graf G = (V,E) betegnes deck(G) som mengden av subgrafer G − v for alle v i V, der G − v oppnås ved å fjerne v og alle tilknyttede kanter.

Rekonstruksjonskonjekturen, som ble formulert uavhengig av Stanislaw Ulam og, i grafteori-sammenheng, av Alvin Kelly på 1940- og 1950-tallet, sier at enhver enkel graf med minst tre noder er rekonstruerbar fra sitt deck; at to grafer som har like deck er isomorfe. Med andre ord skulle grafens struktur være bestemt av samlingen av alle vertex-deleted subgrafer.

Status og utbredte resultater. Konjekturen er fortsatt uløst i full generalitet. Den er bekreftet for enkelte grafklasser, blant annet for trær og flere andre spesifikke typer grafer, og den har blitt grundig undersøkt og verifisert for mange små grafer ved datamaskinberegninger. Likevel finnes det per i dag ingen allmenkunnig bevis, og ingen kjente moteksempler som bryter rekonstruksjonen, noe som gjør problemet til et sentralt åpent spørsmål i moderne grafteori.

Relaterte problemstillinger omfatter kantrekonstruksjon, der man undersøker om en graf kan rekonstrueres fra subgrafer som oppstår ved å fjerne kanter i stedet for noder, samt varianter der subgrafer er ukjente eller delvis mer komplekse.