Mindre (grafteori)

Begrebet mindre i en graf er et begreb med grafteori . Det blev defineret og undersøgt af Robertson og Seymour i en serie artikler med titlen Graph minors (I til XXIII), offentliggjort i Journal of Combinatorial Theory mellem 1983 og 2011.

Definition

En graf er en mindreårig af den endelige og ikke-rettede graf, hvis den kan opnås ved at samle kanterne på en undergraf af . Med andre ord kan fås ved at udføre et vilkårligt antal af følgende operationer: H{\ displaystyle H}G{\ displaystyle G}G{\ displaystyle G}H{\ displaystyle H}G{\ displaystyle G}

• sletning af et isoleret toppunkt  : toppunktet slettes fra grafen;x{\ displaystyle x}x{\ displaystyle x}
• sletning af en kant  : vi sletter kanten , men dens ender forbliver uændrede;xy{\ displaystyle xy}xy{\ displaystyle xy}
• sammentrækning af en kant  : vi fjerner kanten , de to hjørner og flettes sammen i et toppunkt . Enhver kant eller erstattes af en ny kant . Den samme kant tilføjes ikke to gange (man opretter ikke parallelle kanter).xy{\ displaystyle xy}xy{\ displaystyle xy}x{\ displaystyle x}y{\ displaystyle y}z{\ displaystyle z}tx{\ displaystyle tx}ty{\ displaystyle ty}tz{\ displaystyle tz}

Denne definition er den, der gives af László Lovász . Forskellige men ækvivalente definitioner findes i litteraturen.

• En graf . G{\ displaystyle G}

• En mindreårig af . H{\ displaystyle H}G{\ displaystyle G}

• Passage fra til . G{\ displaystyle G}H{\ displaystyle H}

I eksemplet ovenfor går vi fra en graf til dens mindre ved at fjerne tre kanter (i stiplede linjer), ved at fjerne et isoleret toppunkt og ved at sammentrække en kant (i gråt).

Hjælpeprogram

Et af hjælpeprogrammerne i begrebet mindre er karakteriseringen af ​​bestemte klasser af grafer som at have (eller ikke have) en bestemt graf som mindre. For eksempel indeholder en plan graf hverken ( komplet graf i rækkefølge 5) eller ( komplet topartsgraf i rækkefølge 3) som mindre . The Robertson-Seymour sætning viser, at vi således kan karakterisere alle de grafer, der kan tegnes på en given overflade, som en funktion af et sæt ekskluderede mindreårige. Begrebet mindre gør det også muligt blot at udtrykke bestemte sætninger eller formodninger, såsom Hadwigers formodning, ifølge hvilken enhver graf, hvis komplette graf med hjørner ikke er mindre, kan farves med farver. K5{\ displaystyle K_ {5}}K3,3{\ displaystyle K_ {3,3}}G{\ displaystyle G}k{\ displaystyle k}k-1{\ displaystyle k-1}

Teorien om grafminearbejdere er også knyttet til begrebet trænedbrydning .

Bemærkninger

1. Lovász 2005  ; denne definition kan findes på side 2 i online-dokumentet.

Referencer

• (en) László Lovász , “  Graph Minor Theory  ” , Bull. Bitter. Matematik. Soc. (New Series) , bind.  43, nr .  1,2005, s.  75–86 ( læs online ) [PDF]
• (i) Neil Robertson og Paul Seymour , “  Graph Minors. I. Ekskluderer en skov  ” , Journal of Combinatorial Theory , serie B , bind.  35, n o  1,1983, s.  39–61 ( DOI  10.1016 / 0095-8956 (83) 90079-5 ).Den første af 23 artikler i Graph Minors- serien med titlen Mineurs: exclusion d'une forêt .

Relaterede artikler

• The Robertson-Seymour sætning
• Snark sætning

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">