www.wikidata.de-de.nina.az

Unterteilungsgraph Ein ist in der Graphentheorie ein Graph der durch Kantenunterteilung aus einem anderen Graph entstand

Unterteilungsgraph

Ein Unterteilungsgraph ist in der Graphentheorie ein Graph, der durch Kantenunterteilung aus einem anderen Graph entstanden ist. Zwei Graphen heißen homöomorph, falls sie Unterteilungsgraphen besitzen, die isomorph sind. Unterteilungsgraphen spielen unter anderem im Satz von Kuratowski und in der Hajós-Vermutung eine wichtige Rolle.

Unterteilungsgraph des vollständigen Graphen K5, der durch Unterteilung aller Kanten entsteht

Definitionen Bearbeiten

Unterteilungsgraph Bearbeiten

Kante vor und nach Unterteilung

Sei ein ungerichteter Graph, dann versteht man unter einer Unterteilung einer Kante die Ersetzung dieser Kante durch zwei neue Kanten und , die die beiden Knoten und der entfernten Kante mit einem neuen Knoten verbinden. Auf diese Weise entsteht ein neuer Graph mit der neuen Knotenmenge

und der neuen Kantenmenge

wobei und sind. Ein Unterteilungsgraph eines Graphen ist nun ein Graph, der aus diesem durch (null-, ein- oder mehrmalige) Kantenunterteilung entsteht.

Homöomorphie von Graphen Bearbeiten

Zwei Graphen heißen homöomorph, falls Unterteilungsgraphen dieser beiden Graphen existieren, die zueinander isomorph sind. Als den Homöomorphie-Ursprung eines Graphen bezeichnet man den kleinsten Graph, der zu diesem homöomorph ist. Man kann den Homöomorphie-Ursprung eines Graphen durch wiederholtes Entfernen von Knoten vom Grad zwei (Schleifen ausgenommen) und Einfügen einer Kante, die die beiden Nachbarknoten des entfernten Knoten verbindet, ermitteln. Zwei Graphen sind nun genau dann homöomorph, wenn ihre Homöomorphie-Ursprünge isomorph sind.

Beispiele Bearbeiten

Die folgenden beiden Graphen und sind homöomorph, da sie den gemeinsamen Unterteilungsgraphen besitzen. Der Homöomorphie-Ursprung der beiden Graphen ist der Graph .

Auch alle Kreisgraphen sind für zueinander homöomorph mit dem Graphen als Homöomorphie-Ursprung.

Verwendung Bearbeiten

Unterteilungsgraphen spielen eine wichtige Rolle im Satz von Kuratowski. Nach diesem Satz ist ein endlicher Graph genau dann planar, wenn er keinen Teilgraphen enthält, der durch Unterteilung des vollständigen Graphen oder des vollständig bipartiten Graphen entstanden ist. Des Weiteren dienen sie auch zur Definition von topologischen Minoren.

Siehe auch Bearbeiten

Weblinks Bearbeiten

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 Unterteilungsgraph ist in der Graphentheorie ein Graph der durch Kantenunterteilung aus einem anderen Graph entstanden ist Zwei Graphen heissen homoomorph falls sie Unterteilungsgraphen besitzen die isomorph sind Unterteilungsgraphen spielen unter anderem im Satz von Kuratowski und in der Hajos Vermutung eine wichtige Rolle Unterteilungsgraph des vollstandigen Graphen K5 der durch Unterteilung aller Kanten entsteht Inhaltsverzeichnis 1 Definitionen 1 1 Unterteilungsgraph 1 2 Homoomorphie von Graphen 2 Beispiele 3 Verwendung 4 Siehe auch 5 WeblinksDefinitionen BearbeitenUnterteilungsgraph Bearbeiten nbsp nbsp Kante vor und nach Unterteilung Sei G V E displaystyle G V E nbsp ein ungerichteter Graph dann versteht man unter einer Unterteilung einer Kante e u v E displaystyle e u v in E nbsp die Ersetzung dieser Kante durch zwei neue Kanten e 1 displaystyle e 1 nbsp und e 2 displaystyle e 2 nbsp die die beiden Knoten u displaystyle u nbsp und v displaystyle v nbsp der entfernten Kante mit einem neuen Knoten w V displaystyle w notin V nbsp verbinden Auf diese Weise entsteht ein neuer Graph G V E displaystyle G V E nbsp mit der neuen Knotenmenge V V w displaystyle V V cup w nbsp und der neuen Kantenmenge E E e e 1 e 2 displaystyle E E setminus e cup e 1 e 2 nbsp wobei e 1 u w displaystyle e 1 u w nbsp und e 2 w v displaystyle e 2 w v nbsp sind Ein Unterteilungsgraph eines Graphen ist nun ein Graph der aus diesem durch null ein oder mehrmalige Kantenunterteilung entsteht Homoomorphie von Graphen Bearbeiten Zwei Graphen heissen homoomorph falls Unterteilungsgraphen dieser beiden Graphen existieren die zueinander isomorph sind Als den Homoomorphie Ursprung eines Graphen bezeichnet man den kleinsten Graph der zu diesem homoomorph ist Man kann den Homoomorphie Ursprung eines Graphen durch wiederholtes Entfernen von Knoten vom Grad zwei Schleifen ausgenommen und Einfugen einer Kante die die beiden Nachbarknoten des entfernten Knoten verbindet ermitteln Zwei Graphen sind nun genau dann homoomorph wenn ihre Homoomorphie Ursprunge isomorph sind Beispiele BearbeitenDie folgenden beiden Graphen A displaystyle A nbsp und B displaystyle B nbsp sind homoomorph da sie den gemeinsamen Unterteilungsgraphen C displaystyle C nbsp besitzen Der Homoomorphie Ursprung der beiden Graphen ist der Graph D displaystyle D nbsp nbsp Graph A nbsp Graph B nbsp Gemeinsamer Unterteilungsgraph C nbsp Homoomorphie Ursprung DAuch alle Kreisgraphen C n displaystyle C n nbsp sind fur n 2 displaystyle n geq 2 nbsp zueinander homoomorph mit dem Graphen C 2 displaystyle C 2 nbsp als Homoomorphie Ursprung Verwendung BearbeitenUnterteilungsgraphen spielen eine wichtige Rolle im Satz von Kuratowski Nach diesem Satz ist ein endlicher Graph genau dann planar wenn er keinen Teilgraphen enthalt der durch Unterteilung des vollstandigen Graphen K 5 displaystyle K 5 nbsp oder des vollstandig bipartiten Graphen K 3 3 displaystyle K 3 3 nbsp entstanden ist Des Weiteren dienen sie auch zur Definition von topologischen Minoren Siehe auch BearbeitenKantenkontraktionWeblinks BearbeitenBela Bollobas Subdivision In PlanetMath englisch Ed Pegg Jr Edge splitting In MathWorld englisch Abgerufen von https de wikipedia org w index php title Unterteilungsgraph amp oldid 157954639