www.wikidata.de-de.nina.az

Faktor Graphentheorie Ein Faktor ist in der Graphentheorie ein Teilgraph eines Graphen bei dem gewisse Anforderungen an

Faktor (Graphentheorie)

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.

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

Definition Bearbeiten

Sei ein einfacher Graph und eine Abbildung, die jedem Knoten des Graphen eine natürliche Zahl zuordnet. Ein g-Faktor ist dann ein Teilgraph von mit derselben Knotenmenge wie , in dem jeder Knoten von den Grad besitzt, also genau Nachbarn hat.

Gilt für alle Knoten mit die Bedingung , besitzen also alle Knoten des Teilgraphen genau Nachbarn, spricht man dementsprechend auch von einem a-Faktor. Gilt dagegen für alle Knoten die Bedingung , besitzen also alle Knoten des Teilgraphen mindestens und höchstens 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 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 Knotens eine 1-Faktorisierung möglich wird.

Beispiele Bearbeiten

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

Existenz von Faktoren Bearbeiten

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

Literatur Bearbeiten

  • Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5 (354 S.).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Ein 1 Faktor eines Graphen und damit auch ein perfektes Matching2 Faktor eines GraphenEin weiterer 2 Faktor eines Graphen und auch ein HamiltonkreisEine mogliche 2 faktorisierung von K 5 displaystyle K 5 dem vollstandigen Graphen mit 5 Ecken in zwei 2 faktoren Blau und Rot Inhaltsverzeichnis 1 Definition 1 1 Aquivalente Definition 1 2 Verwandte Begriffe 2 Beispiele 3 Existenz von Faktoren 4 LiteraturDefinition BearbeitenSei G V E displaystyle G V E nbsp ein einfacher Graph und g V N 0 displaystyle g colon V rightarrow mathbb N 0 nbsp eine Abbildung die jedem Knoten des Graphen eine naturliche Zahl zuordnet Ein g Faktor F displaystyle F nbsp ist dann ein Teilgraph von G displaystyle G nbsp mit derselben Knotenmenge V displaystyle V nbsp wie G displaystyle G nbsp in dem jeder Knoten v i displaystyle v i nbsp von F displaystyle F nbsp den Grad g v i displaystyle g v i nbsp besitzt also genau g v i displaystyle g v i nbsp Nachbarn hat Gilt fur alle Knoten v i displaystyle v i nbsp mit i 1 V displaystyle i 1 ldots V nbsp die Bedingung g v i a displaystyle g v i a nbsp besitzen also alle Knoten des Teilgraphen genau a displaystyle a nbsp Nachbarn spricht man dementsprechend auch von einem a Faktor Gilt dagegen fur alle Knoten v i displaystyle v i nbsp die Bedingung a g v i b displaystyle a leq g v i leq b nbsp besitzen also alle Knoten des Teilgraphen mindestens a displaystyle a nbsp und hochstens b displaystyle b nbsp Nachbarn spricht man entsprechend von einem a b Faktor Aquivalente Definition Bearbeiten Aquivalent zur obigen Definition ist die folgende Einen a regularen Teilgraph der den Graph G displaystyle G nbsp aufspannt nennt man a Faktor Verwandte Begriffe Bearbeiten Eine Zerlegung eines Graphen in a Faktoren wird a Faktorisierung genannt Ein nichtleerer Graph heisst faktor kritisch wenn durch Wegnahme eines beliebigen Knotens eine 1 Faktorisierung moglich wird Beispiele BearbeitenEine Paarung ist ein 0 1 displaystyle 0 1 nbsp Faktor also ein Teilgraph von G displaystyle G nbsp in dem jeder Knoten x displaystyle x nbsp hochstens einen Nachbarn hat Eine perfekte Paarung ist dagegen ein 1 Faktor also ein Teilgraph von G displaystyle G nbsp in dem jeder Knoten x displaystyle x nbsp genau einen Nachbarn besitzt Hamiltonsche Graphen schliesslich besitzen 2 Faktoren in denen jeder Knoten x displaystyle x nbsp genau zwei Nachbarn hat Existenz von Faktoren BearbeitenDer 1 Faktor Satz von Tutte besagt dass man aus G displaystyle G nbsp und g displaystyle g nbsp einen Graphen G displaystyle G nbsp konstruieren kann welcher genau dann einen 1 Faktor besitzt wenn G displaystyle G nbsp einen g displaystyle g nbsp Faktor besitzt Dies ist die Definition einer Reduktion im Sinne der theoretischen Informatik Da umgekehrt 1 Faktoren Spezialfalle von g displaystyle g nbsp Faktoren sind ist das g displaystyle g nbsp Faktorproblem aquivalent zum 1 Faktorproblem Literatur BearbeitenReinhard Diestel Graphentheorie Springer Berlin 2010 ISBN 978 3 642 14911 5 354 S Abgerufen von https de wikipedia org w index php title Faktor Graphentheorie amp oldid 225888816