Faktor (Graphentheorie)

Ein 1-Faktor eines Graphen und damit auch ein perfektes Matching

2-Faktor eines Graphen

Ein weiterer 2-Faktor eines Graphen und auch ein Hamiltonkreis

Eine mögliche 2-faktorisierung von $K_5$ (dem vollständigen Graphen mit 5 Ecken) in zwei 2-faktoren (Blau und Rot)

Ein Faktor ist in der Graphentheorie ein Teilgraph eines Graphen, bei dem gewisse Anforderungen an den Grad der Knoten sowie an den Zusammenhang des Graphen gestellt werden. Faktoren spielen eine wichtige Rolle in der Theorie des Matching-Problems und des Hamiltonkreisproblems.

Definition

Sei $G=(V,E)$ ein einfacher Graph und $g:V\to {\mathbb{N}}_0$ eine Abbildung, die jedem Knoten des Graphen eine natürliche Zahl zuordnet. Ein g-Faktor $F$ ist dann ein Teilgraph von $G$ mit derselben Knotenmenge $V$ wie $G$, in dem jeder Knoten $v_i$ von $F$ den Grad $g(v_i)$ besitzt, also genau $g(v_i)$ Nachbarn hat.

Gilt für alle Knoten $v_i$ mit $i=1,\dots ,|V|$ die Bedingung $g(v_i)=a$, besitzen also alle Knoten des Teilgraphen genau $a$ Nachbarn, spricht man dementsprechend auch von einem a-Faktor. Gilt dagegen für alle Knoten $v_i$ die Bedingung $a\le g(v_i)\le b$, besitzen also alle Knoten des Teilgraphen mindestens $a$ und höchstens $b$ Nachbarn, spricht man entsprechend von einem [a,b]-Faktor.

Äquivalente Definition

Äquivalent zur obigen Definition ist die folgende: Einen a-regulären Teilgraph, der den Graph $G$ aufspannt, nennt man a-Faktor.

Verwandte Begriffe

Eine Zerlegung eines Graphen in a-Faktoren wird a-Faktorisierung genannt. Ein nichtleerer Graph heißt faktor-kritisch, wenn durch Wegnahme eines beliebigen Knotens eine 1-Faktorisierung möglich wird.

Beispiele

Eine Paarung ist ein $[0,1]$-Faktor, also ein Teilgraph von $G$, in dem jeder Knoten $x$ höchstens einen Nachbarn hat. Eine perfekte Paarung ist dagegen ein 1-Faktor, also ein Teilgraph von $G$, in dem jeder Knoten $x$ genau einen Nachbarn besitzt. Hamiltonsche Graphen schließlich besitzen 2-Faktoren, in denen jeder Knoten $x$ genau zwei Nachbarn hat.

Existenz von Faktoren

Der 1-Faktor-Satz von Tutte besagt, dass man aus $G$ und $g$ einen Graphen $G^{*}$ konstruieren kann, welcher genau dann einen 1-Faktor besitzt, wenn $G$ einen $g$-Faktor besitzt. Dies ist die Definition einer Reduktion im Sinne der theoretischen Informatik. Da umgekehrt 1-Faktoren Spezialfälle von $g$-Faktoren sind, ist das $g$-Faktorproblem äquivalent zum 1-Faktorproblem.

Literatur

• Vorlage:Literatur