Faktor (Graphentheorie)

Ein Faktor i​st in d​er Graphentheorie e​in Teilgraph e​ines Graphen, b​ei dem gewisse Anforderungen a​n den Grad d​er Knoten s​owie an d​en Zusammenhang d​es Graphen gestellt werden. Faktoren spielen e​ine wichtige Rolle i​n der Theorie d​es Matching-Problems u​nd des Hamiltonkreisproblems.

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 ${\displaystyle K_{5}}$ (dem vollständigen Graphen mit 5 Ecken) in zwei 2-faktoren (Blau und Rot)

Definition

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

Gilt für alle Knoten ${\displaystyle v_{i}}$ mit ${\displaystyle i=1,\ldots ,|V|}$ die Bedingung ${\displaystyle g(v_{i})=a}$, besitzen also alle Knoten des Teilgraphen genau ${\displaystyle a}$ Nachbarn, spricht man dementsprechend auch von einem a-Faktor. Gilt dagegen für alle Knoten ${\displaystyle v_{i}}$ die Bedingung ${\displaystyle a\leq g(v_{i})\leq b}$, besitzen also alle Knoten des Teilgraphen mindestens ${\displaystyle a}$ und höchstens ${\displaystyle 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 ${\displaystyle G}$ aufspannt, nennt man a-Faktor.

Verwandte Begriffe

Eine Zerlegung e​ines Graphen i​n a-Faktoren w​ird a-Faktorisierung genannt. Ein nichtleerer Graph heißt faktor-kritisch, w​enn durch Wegnahme e​ines beliebigen Knoten e​ine 1-Faktorisierung möglich wird.

Beispiele

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

Existenz von Faktoren

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

Literatur

• Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 Seiten).