Faktor (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
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[Bearbeiten]

Sei G=(V, E) ein einfacher Graph und g:V \rightarrow \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, \ldots , |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 \leq g(v_i) \leq b, besitzen also alle Knoten des Teilgraphen mindestens a und höchstens b Nachbarn, spricht man entsprechend von einem [a,b]-Faktor.

Äquivalente Definition[Bearbeiten]

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

Verwandte Begriffe[Bearbeiten]

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

Beispiele[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]