Graph-Theorie ist ein wachsendes Gebiet in der mathematischen Forschung, und hat ein großes Spezialvokabular. Einige Autoren verwenden dasselbe Wort mit verschiedenen Bedeutungen. Einige Autoren verwenden verschiedene Wörter, um dasselbe Ding zu bedeuten. Diese Seite versucht, mit aktuellem Gebrauch Schritt zu halten.

Grundlagen

Ein Graph G besteht aus zwei Typen von Elementen, nämlich Scheitelpunkte und Ränder. Jeder Rand hat zwei Endpunkte im Satz von Scheitelpunkten und wird gesagt, sich die zwei Endpunkte zu verbinden oder ihnen anzuschließen. Ein Rand kann so als eine Reihe zwei Scheitelpunkte definiert werden (oder ein befohlenes Paar, im Fall von einem geleiteten Graphen - sieh Abteilungsrichtung).

Alternative Modelle von Graphen bestehen; z.B kann von einem Graphen als Boolean binäre Funktion über den Satz von Scheitelpunkten oder als ein Quadrat (0,1) - Matrix gedacht werden.

Ein Scheitelpunkt wird einfach als ein Knoten oder ein Punkt gezogen. Der Scheitelpunkt-Satz von G wird gewöhnlich durch V (G), oder V angezeigt, wenn es keine Gefahr der Verwirrung gibt. Die Ordnung eines Graphen ist die Zahl seiner Scheitelpunkte, d. h. |V (G) |.

Ein Rand (eine Reihe zwei Elemente) wird als eine Linie gezogen, die zwei Scheitelpunkte, genannt Endpunkte oder (weniger häufig) endvertices verbindet. Ein Rand mit endvertices x und y wird durch xy (ohne jedes Symbol zwischen) angezeigt. Der Rand-Satz von G wird gewöhnlich durch E (G) oder E angezeigt, wenn es keine Gefahr der Verwirrung gibt.

Die Größe eines Graphen ist die Zahl seiner Ränder, d. h. |E (G) |.

Eine Schleife ist ein Rand, dessen Endpunkte derselbe Scheitelpunkt sind. Eine Verbindung hat zwei verschiedene endvertices. Ein Rand ist vielfach, wenn es einen anderen Rand mit demselben endvertices gibt; sonst ist es einfach. Die Vielfältigkeit eines Randes ist die Zahl von vielfachen Rändern, die dieselben Endscheitelpunkte teilen; die Vielfältigkeit eines Graphen, die maximale Vielfältigkeit seiner Ränder. Ein Graph ist ein einfacher Graph, wenn er keine vielfachen Ränder oder Schleifen, ein Mehrgraph hat, wenn er vielfache Ränder, aber keine Schleifen, und einen Mehrgraphen oder Pseudographen hat, wenn er sowohl vielfache Ränder als auch Schleifen enthält (ist die Literatur hoch inkonsequent). Wenn festgesetzt, ohne jede Qualifikation, wie man fast immer annimmt, ist ein Graph einfacher muss nach dem Zusammenhang urteilen.

Graphen, deren Ränder oder Scheitelpunkte Namen oder Etiketten haben, sind wie etikettiert, diejenigen ohne, wie unetikettiert, bekannt. Graphen mit etikettierten Scheitelpunkten werden nur Scheitelpunkt-etikettiert, diejenigen mit etikettierten Rändern werden nur Rand-etikettiert. Der Unterschied zwischen einem etikettierten und einem unetikettierten Graphen ist, dass der Letztere keinen spezifischen Satz von Scheitelpunkten oder Rändern hat; es wird als eine andere Weise betrachtet, einen Isomorphismus-Typ von Graphen zu betrachten. (So unterscheidet dieser Gebrauch zwischen Graphen mit identifizierbarem Scheitelpunkt oder Rand-Sätzen einerseits, und Isomorphismus-Typen oder Klassen von Graphen auf dem anderen.)

(Graph, der gewöhnlich etikettiert, bezieht sich auf die Anweisung von Etiketten (gewöhnlich natürliche Zahlen, gewöhnlich verschieden) zu den Rändern und Scheitelpunkten eines Graphen, Themas bestimmten Regeln abhängig von der Situation. Das sollte damit nicht verwirrt sein, verschiedene Etiketten oder Namen auf den Scheitelpunkten Graphen bloß zu haben.)

Ein Hyperrand ist ein Rand, dem erlaubt wird, jede Zahl von Scheitelpunkten, vielleicht mehr als 2 zu übernehmen. Ein Graph, der jeden Hyperrand erlaubt, wird einen Hypergraphen genannt. Ein einfacher Graph kann ein spezieller Fall des Hypergraphen, nämlich der 2-Uniformen-Hypergraph in Betracht gezogen werden. Jedoch, wenn festgesetzt, ohne jede Qualifikation, wie man immer annimmt, besteht ein Rand aus höchstens 2 Scheitelpunkten, und ein Graph ist mit einem Hypergraphen nie verwirrt.

Ein Nichtrand (oder Antirand) sind ein Rand, der im Graphen nicht da ist. Mehr formell, für zwei Scheitelpunkte und, ist ein Nichtrand in einem Graphen, wann auch immer nicht ein Rand darin ist. Das bedeutet, dass es entweder keinen Rand zwischen den zwei Scheitelpunkten oder (für geleitete Graphen) am grössten Teil von einen dessen gibt und davon ein Kreisbogen in G ist.

Gelegentlich werden der Begriff cotriangle oder das Antidreieck für eine Reihe drei Scheitelpunkte verwendet, von denen keiner verbunden wird.

Die Ergänzung eines Graphen G ist ein Graph mit demselben Scheitelpunkt-Satz, wie G, aber mit einem Rand solch untergeht, dass xy ein Rand darin ist, wenn, und nur wenn xy nicht ein Rand in G ist.

Ein edgeless Graph oder leerer Graph oder ungültiger Graph sind ein Graph mit der Null oder mehr Scheitelpunkten, aber keinen Rändern. Der leere Graph oder ungültige Graph können auch der Graph ohne Scheitelpunkte und keine Ränder sein. Wenn es ein Graph ohne Ränder und eine Zahl von Scheitelpunkten ist, kann es den ungültigen Graphen auf Scheitelpunkten genannt werden. (Es gibt keine Konsistenz überhaupt in der Literatur.)

Ein Graph ist unendlich, wenn er ungeheuer viele Scheitelpunkte oder Ränder oder beide hat; sonst ist der Graph begrenzt. Ein unendlicher Graph, wo jeder Scheitelpunkt begrenzten Grad hat, wird lokal begrenzt genannt. Wenn festgesetzt, ohne jede Qualifikation, wie man gewöhnlich annimmt, ist ein Graph begrenzt. Siehe auch dauernden Graphen.

Wie man

gesagt wird, sind zwei Graphen G und H isomorph, durch G ~ H angezeigt, wenn es eine isomorphe Ähnlichkeit, genannt einen Isomorphismus zwischen den Scheitelpunkten des solchen Graphen gibt, dass zwei Scheitelpunkte in G angrenzend sind, wenn, und nur wenn ihre entsprechenden Scheitelpunkte in H angrenzend sind. Ebenfalls, wie man sagt, ist ein Graph G homomorphic zu einem Graphen H, wenn es gibt, genannt einen Homomorphismus, von V (G) zu V solcher (H) kartografisch darzustellen, dass, wenn zwei Scheitelpunkte in G dann angrenzend sind, ihre entsprechenden Scheitelpunkte in H angrenzend sind.

Subgraphen

Ein Subgraph eines Graphen G ist ein Graph, dessen Scheitelpunkt-Satz eine Teilmenge von diesem von G ist, und dessen Angrenzen-Beziehung eine Teilmenge von diesem von auf diese Teilmenge eingeschränkten G ist. In der anderen Richtung ist ein Supergraph eines Graphen G ein Graph, dessen G ein Subgraph ist. Wir sagen, dass ein Graph G einen anderen Graphen H enthält, wenn ein Subgraph von G H ist oder zu H isomorph ist.

Ein Subgraph H ist ein Überspannen-Subgraph oder Faktor, von einem Graphen G, wenn er denselben Scheitelpunkt wie G setzen lassen hat. Wir sagen, dass H G abmisst.

Wie man

sagt, wird ein Subgraph H eines Graphen G veranlasst, wenn, für ein Paar von Scheitelpunkten x und y von H, xy ein Rand von H ist, wenn, und nur wenn xy ein Rand von G ist. Mit anderen Worten ist H ein veranlasster Subgraph von G, wenn es genau die Ränder hat, die in G über denselben Scheitelpunkt-Satz erscheinen. Wenn der Scheitelpunkt-Satz von H die Teilmenge S V (G) ist, dann kann H als G [S] geschrieben werden und wird gesagt, durch S veranlasst zu werden.

Wie man

sagt, ist ein Graph, der H als ein veranlasster Subgraph nicht enthält, H-free'.

Ein universaler Graph in einer Klasse K von Graphen ist ein einfacher Graph, in dem jedes Element in K als ein Subgraph eingebettet werden kann.

Ein Graph G ist mit einem Eigentum P minimal vorausgesetzt, dass G Eigentum P hat und kein richtiger Subgraph von G Eigentum P hat. In dieser Definition, wie man gewöhnlich versteht, bedeutet der Begriff Subgraph "veranlassten Subgraphen." Der Begriff von maximality wird Doppel-definiert: G ist mit P maximal vorausgesetzt, dass P (G) und G keinen Supergraphen H solch dass P (H) hat.

Viele wichtige Klassen von Graphen können durch Sätze von verbotenen Subgraphen, die minimalen Graphen definiert werden, die nicht in der Klasse sind.

Spaziergänge

Ein Spaziergang ist eine Wechselfolge von Scheitelpunkten und Rändern, beginnend und mit einem Scheitelpunkt endend, wo jeder Scheitelpunkt Ereignis sowohl zum Rand ist, der ihm als auch der Rand vorangeht, der ihm in der Folge folgt, und wo die Scheitelpunkte, die vorangehen und einem Rand folgen, die Endscheitelpunkte dieses Randes sind. Ein Spaziergang wird geschlossen, wenn sein vor allen Dingen Scheitelpunkte dasselbe, und offen sind, wenn sie verschieden sind.

Die Länge l eines Spaziergangs ist die Zahl von Rändern, die es verwendet. Für einen offenen Spaziergang, l = n-1, wo n die Zahl von besuchten Scheitelpunkten ist (wird ein Scheitelpunkt jedes Mal aufgezählt, wird er besucht). Für einen geschlossenen Spaziergang, l = n (wird der Scheitelpunkt des Anfangs/Endes zweimal verzeichnet, aber wird zweimal nicht aufgezählt). Im Beispiel-Graphen, (1, 2, 5, 1, 2, 3) ist ein offener Spaziergang mit der Länge 5, und (4, 5, 2, 1, 5, 4) ist ein geschlossener Spaziergang der Länge 5.

Eine Spur ist ein Spaziergang, in dem alle Ränder verschieden sind. Eine geschlossene Spur ist eine Tour oder Stromkreis genannt worden, aber diese sind nicht universal, und der Letztere wird häufig für einen regelmäßigen Subgraphen des Grads zwei vorbestellt.

Traditionell hat sich ein Pfad darauf bezogen, was jetzt gewöhnlich als ein offener Spaziergang bekannt ist. Heutzutage, wenn festgesetzt, ohne jede Qualifikation, wie man gewöhnlich versteht, ist ein Pfad einfach, bedeutend, dass keine Scheitelpunkte (und so keine Ränder) wiederholt werden. (Der Begriff Kette ist auch gebraucht worden, um sich auf einen Spaziergang zu beziehen, in dem alle Scheitelpunkte und Ränder verschieden sind.) Im Beispiel-Graphen, (5, 2, 1) ist ein Pfad der Länge 2. Die geschlossene Entsprechung zu diesem Typ des Spaziergangs, ein Spaziergang, der anfängt und an demselben Scheitelpunkt endet, aber sonst keine wiederholten Scheitelpunkte oder Ränder hat, wird einen Zyklus genannt. Wie Pfad hat sich dieser Begriff traditionell auf jeden geschlossenen Spaziergang bezogen, aber wird gewöhnlich jetzt verstanden, definitionsgemäß einfach zu sein. Im Beispiel-Graphen, (1, 5, 2, 1) ist ein Zyklus der Länge 3. (Einem Zyklus, verschieden von einem Pfad, wird nicht erlaubt, Länge 0 zu haben.) Pfade und Zyklen von n Scheitelpunkten werden häufig durch P und C beziehungsweise angezeigt. (Einige Autoren verwenden die Länge statt der Zahl von Scheitelpunkten jedoch.)

C ist eine Schleife, C ist ein digon (ein Paar von parallelen ungeleiteten Rändern in einem Mehrgraphen oder ein Paar von antiparallelen Rändern in einem geleiteten Graphen), und C wird ein Dreieck genannt.

Ein Zyklus, der sonderbare Länge hat, ist ein sonderbarer Zyklus; sonst ist es ein gleicher Zyklus. Ein Lehrsatz ist, dass ein Graph zweiteilig ist, wenn, und nur wenn er keine sonderbaren Zyklen enthält. (Sieh ganzen zweiteiligen Graphen.)

Ein Graph ist acyclic, wenn es keine Zyklen enthält; unicyclic, wenn es genau einen Zyklus enthält; und pancyclic, wenn es Zyklen jeder möglichen Länge (von 3 bis die Ordnung des Graphen) enthält.

Der Umfang eines Graphen ist die Länge eines kürzesten (einfachen) Zyklus im Graphen; und der Kreisumfang, die Länge eines längsten (einfachen) Zyklus. Der Umfang und Kreisumfang eines acyclic Graphen werden definiert, um Unendlichkeit  zu sein.

Ein Pfad oder Zyklus sind Hamiltonian (oder abmessend), wenn es alle Scheitelpunkte genau einmal verwendet. Ein Graph, der einen Pfad von Hamiltonian enthält, ist nachweisbar; und derjenige, der einen Pfad von Hamiltonian für jedes gegebene Paar von (verschiedenen) Endscheitelpunkten enthält, ist verbundener Graph von Hamiltonian. Ein Graph, der einen Zyklus von Hamiltonian enthält, ist ein Graph von Hamiltonian.

Eine Spur oder Stromkreis (oder Zyklus) sind Eulerian, wenn es alle Ränder genau einmal verwendet. Ein Graph, der eine Spur von Eulerian enthält, ist überquerbar. Ein Graph, der einen Stromkreis von Eulerian enthält, ist ein Graph von Eulerian.

Zwei Pfade sind innerlich zusammenhanglos (einige Menschen nennen es unabhängig), wenn sie keinen Scheitelpunkt gemeinsam haben, außer vor allen Dingen.

Ein theta Graph ist die Vereinigung von drei innerlich zusammenhanglosen (einfachen) Pfaden, die dieselben zwei verschiedenen Endscheitelpunkte haben. Ein theta Graph hat sieben Scheitelpunkte, die als die Scheitelpunkte eines regelmäßigen Sechseckes plus ein zusätzlicher Scheitelpunkt im Zentrum eingeordnet werden können. Die acht Ränder sind der Umfang des Sechseckes plus ein Diameter.

Bäume

Ein Baum ist ein verbundener acyclic einfacher Graph. Für geleitete Graphen hat jeder Scheitelpunkt am grössten Teil eines eingehenden Randes. Ein Scheitelpunkt des Grads 1 wird ein Blatt oder Hängescheitelpunkt genannt. Ein Rand-Ereignis zu einem Blatt ist ein Blattrand oder Hängerand. (Einige Menschen definieren einen Blattrand als ein Blatt und definieren dann einen Blatt-Scheitelpunkt obendrein. Diese zwei Sätze von Definitionen werden häufig austauschbar verwendet.) Ein Nichtblatt-Scheitelpunkt ist ein innerer Scheitelpunkt. Manchmal ist ein Scheitelpunkt des Baums bemerkenswert, und die Wurzel genannt; in diesem Fall wird der Baum eingewurzelt genannt. Eingewurzelte Bäume werden häufig, wie geleitet, acyclic Graphen mit den Rändern behandelt, die weg von der Wurzel hinweisen.

Ein Subbaum des Baums T ist ein verbundener Subgraph von T.

Ein Wald ist ein acyclic einfacher Graph. Für geleitete Graphen hat jeder Scheitelpunkt am grössten Teil eines eingehenden Randes. (D. h. ein Baum mit der Konnektivitätsvoraussetzung ist umgezogen; ein Graph, der vielfache getrennte Bäume enthält.)

Ein Subwald des Waldes F ist ein Subgraph von F.

Ein Überspannen-Baum ist ein Überspannen-Subgraph, der ein Baum ist. Jeder Graph hat einen Überspannen-Wald. Aber nur ein verbundene Graph hat einen Überspannen-Baum.

Eine spezielle Art des Baums hat gerufen ein Stern ist K. Ein veranlasster Stern mit 3 Rändern ist eine Klaue.

Eine Raupe ist ein Baum, in dem alle Nichtblatt-Knoten einen einzelnen Pfad bilden.

Ein k-ary' Baum ist ein eingewurzelter Baum, in dem jeder innere Scheitelpunkt k Kinder hat. Ein 1-ary Baum ist gerade ein Pfad. Ein 2-ary Baum wird auch einen binären Baum genannt.

Cliquen

Der ganze Graph K des Auftrags n ist ein einfacher Graph mit n Scheitelpunkten, in denen jeder Scheitelpunkt neben jeder anderem ist. Der Beispiel-Graph ist nach rechts abgeschlossen. Der ganze Graph auf n Scheitelpunkten wird häufig durch K angezeigt. Es hat n (n-1)/2 Ränder (entsprechend allen möglichen Wahlen von Paaren von Scheitelpunkten).

Eine Clique in einem Graphen ist eine Reihe pairwise angrenzender Scheitelpunkte. Da jeder von einer Clique veranlasste Subgraph ein ganzer Subgraph ist, werden die zwei Begriffe und ihre Notationen gewöhnlich austauschbar verwendet. Eine K-Clique' ist eine Clique des Auftrags k. Im Beispiel-Graphen oben bilden Scheitelpunkte 1, 2 und 5 einen 3-Cliquen-, oder ein Dreieck. Eine maximale Clique ist eine Clique, die nicht eine Teilmenge jeder anderen Clique ist (einige Autoren bestellen den Begriff Clique für maximale Cliquen vor).

Die Clique-Zahl ω (G) eines Graphen G ist die Ordnung einer größten Clique in G.

Stark verbundener Bestandteil

Ein zusammenhängendes, aber schwächeres Konzept ist das eines stark verbundenen Bestandteils. Informell ist ein stark verbundener Bestandteil eines geleiteten Graphen ein Subgraph, wo alle Knoten im Subgraphen durch alle anderen Knoten im Subgraphen erreichbar sind. Reachability zwischen Knoten wird durch die Existenz eines Pfads zwischen den Knoten gegründet.

Ein geleiteter Graph kann in stark verbundene Bestandteile durch das Laufen des Algorithmus der Tiefensuche (DFS) zweimal zersetzt werden: erstens, auf dem Graphen selbst und als nächstes auf dem umstellen Graphen in der abnehmenden Ordnung der Beendigungen des ersten DFS. In Anbetracht eines geleiteten Graphen G ist das Umstellen G der Graph G mit allen umgekehrten Rand-Richtungen.

Knoten

Ein Knoten in einem geleiteten Graphen ist eine Sammlung von Scheitelpunkten und Rändern mit dem Eigentum, dass jeder Scheitelpunkt im Knoten aus dem Amt scheide Ränder und alle aus dem Amt scheiden Ränder von Scheitelpunkten im Knoten hat, der an anderen Scheitelpunkten im Knoten begrenzt ist. So ist es unmöglich, den Knoten zu verlassen, während man den Richtungen der Ränder folgt.

Minderjährige

Ein Minderjähriger dessen ist eine Einspritzung von zum solchem, dass jeder Rand darin einem Pfad (zusammenhanglos von allen anderen solchen Pfaden) im solchem entspricht, dass jeder Scheitelpunkt darin in einem oder mehr Pfaden ist, oder ein Teil der Einspritzung von dazu ist. Das kann in Bezug auf Zusammenziehungen wechselweise ausgedrückt werden, die Operationen sind, die ein Pfad und alle Scheitelpunkte darauf in einen einzelnen Rand zusammenbrechen (sieh Gering (Graph-Theorie)).

Das Einbetten

Ein Einbetten dessen ist eine Einspritzung von zum solchem, dass jeder Rand darin einem Pfad (zusammenhanglos von allen anderen solchen Pfaden) darin entspricht.

Angrenzen und Grad

In der Graph-Theorie ist Grad, besonders dieser eines Scheitelpunkts, gewöhnlich ein Maß des unmittelbaren Angrenzens.

Ein Rand verbindet zwei Scheitelpunkte; wie man sagt, sind diese zwei Scheitelpunkte Ereignis zu diesem Rand, oder, gleichwertig, dieses Rand-Ereignis zu jenen zwei Scheitelpunkten. Alle Grad-zusammenhängenden Konzepte sind mit Angrenzen oder Vorkommen verbunden.

Der Grad oder Valenz, d (v) eines Scheitelpunkts v in einem Graphen G ist die Zahl des Rand-Ereignisses zu v mit Schleifen, die zweimal aufzählen werden. Ein Scheitelpunkt des Grads 0 ist ein isolierter Scheitelpunkt. Ein Scheitelpunkt des Grads 1 ist ein Blatt. Im etikettierten einfachen Graph-Beispiel haben Scheitelpunkte 1 und 3 einen Grad 2, Scheitelpunkte 2, 4 und 5 haben einen Grad 3, und Scheitelpunkt 6 hat einen Grad 1. Wenn E begrenzt ist, dann ist die Gesamtsumme von Scheitelpunkt-Graden zweimal der Zahl von Rändern gleich.

Der Gesamtgrad eines Graphen ist zweimal der Zahl von Rändern, eingeschlossene Schleifen gleich. Das bedeutet, dass für einen Graphen mit 3 Scheitelpunkten mit jedem Scheitelpunkt, der einen Grad zwei (d. h. ein Dreieck) hat, der Gesamtgrad sechs (z.B 3 x 2 = 6) sein würde. Die allgemeine Formel dafür ist Gesamtgrad = 2n wo n = Zahl von Rändern.

Eine Grad-Folge ist eine Liste von Graden eines Graphen in der nichtzunehmenden Ordnung (z.B d  d  …  d). Eine Folge von nichtzunehmenden ganzen Zahlen ist realisierbar, wenn es eine Grad-Folge von einem Graphen ist.

Zwei Scheitelpunkte u und v werden angrenzend genannt, wenn ein Rand zwischen ihnen besteht. Wir zeigen das durch u ~ v oder u  v an. Im obengenannten Graphen sind Scheitelpunkte 1 und 2 angrenzend, aber Scheitelpunkte 2 und 4 sind nicht. Der Satz von Nachbarn von v, d. h. Scheitelpunkten neben v nicht einschließlich v selbst, formt sich ein veranlasster Subgraph hat die (offene) Nachbarschaft von v genannt und hat N (v) angezeigt. Wenn v auch eingeschlossen wird, wird es eine geschlossene Nachbarschaft genannt und durch N [v] angezeigt. Wenn festgesetzt, ohne jede Qualifikation, wie man annimmt, ist eine Nachbarschaft offen. Die Subschrift G ist gewöhnlich fallen gelassen, wenn es keine Gefahr der Verwirrung gibt; dieselbe Nachbarschaft-Notation kann auch verwendet werden, um sich auf Sätze von angrenzenden Scheitelpunkten aber nicht den entsprechenden veranlassten Subgraphen zu beziehen. Im Beispiel-Graphen hat Scheitelpunkt 1 zwei Nachbarn: Scheitelpunkte 2 und 5. Für einen einfachen Graphen fällt die Zahl von Nachbarn, die ein Scheitelpunkt hat, mit seinem Grad zusammen.

Ein vorherrschender Satz eines Graphen ist eine Scheitelpunkt-Teilmenge, deren geschlossene Nachbarschaft alle Scheitelpunkte des Graphen einschließt. Ein Scheitelpunkt v beherrscht einen anderen Scheitelpunkt u, wenn es einen Rand von v bis u gibt. Eine Scheitelpunkt-Teilmenge V beherrscht eine andere Scheitelpunkt-Teilmenge U, wenn jeder Scheitelpunkt in U neben einem Scheitelpunkt in V ist. Die minimale Größe eines vorherrschenden Satzes ist die Überlegenheitszahl γ (G).

In Computern, ein begrenzter, geleiteter oder ungeleiteter Graph (mit n Scheitelpunkten, sagen) wird häufig durch seine Angrenzen-Matrix vertreten: Eine n-by-n Matrix, deren Zugang in der Reihe i und Spalte j die Zahl von Rändern vom i-th bis den j-th Scheitelpunkt gibt.

Geisterhafte Graph-Theorie-Studienbeziehungen zwischen den Eigenschaften eines Graphen und seiner Angrenzen-Matrix oder anderen matrices haben mit dem Graphen verkehrt.

Der maximale Grad Δ (G) eines Graphen G ist der größte Grad über alle Scheitelpunkte; der minimale Grad δ (G), das kleinste.

Ein Graph, in dem jeder Scheitelpunkt denselben Grad hat, ist regelmäßig. Es ist k-regular', wenn jeder Scheitelpunkt Grad k hat. Ein 0-regelmäßiger Graph ist ein unabhängiger Satz. Ein 1-regelmäßiger Graph ist ein Zusammenbringen. Ein 2-regelmäßiger Graph ist ein Scheitelpunkt zusammenhanglose Vereinigung von Zyklen. Wie man sagt, ist ein 3-regelmäßiger Graph kubisch, oder dreiwertig.

Ein K-Faktor']] ist ein k-regular das Überspannen des Subgraphen. Ein 1 Faktor ist ein vollkommenes Zusammenbringen. Eine Teilung von Rändern eines Graphen in K-Faktoren wird einen k-factorization genannt'. Ein k-factorable Graph' ist ein Graph, der einen k-factorization zulässt.

Ein Graph ist biregular, wenn es ungleiche maximale und minimale Grade hat und jeder Scheitelpunkt einen jener zwei Grade hat.

Ein stark regelmäßiger Graph ist ein regelmäßiger solcher Graph, dass irgendwelche angrenzenden Scheitelpunkte dieselbe Zahl von allgemeinen Nachbarn wie andere angrenzende Paare haben, und dass irgendwelche nichtangrenzenden Scheitelpunkte dieselbe Zahl von allgemeinen Nachbarn wie andere nichtangrenzende Paare haben.

Unabhängigkeit

In der Graph-Theorie trägt das Wort unabhängig gewöhnlich die Konnotation von pairwise zusammenhanglos oder gegenseitig nichtangrenzend. In diesem Sinn ist Unabhängigkeit eine Form des unmittelbaren Nichtangrenzens. Ein isolierter Scheitelpunkt ist ein Scheitelpunkt nicht Ereignis zu irgendwelchen Rändern. Ein unabhängiger Satz, oder coclique, oder stabiler Satz oder staset, ist eine Reihe von Scheitelpunkten, von denen kein Paar angrenzend ist. Da der durch jeden unabhängigen Satz veranlasste Graph ein leerer Graph ist, werden die zwei Begriffe gewöhnlich austauschbar gebraucht. Im Beispiel oben bilden Scheitelpunkte 1, 3, und 6 einen unabhängigen Satz; und 3, 5, und 6 Form ein anderer.

Zwei Subgraphen sind zusammenhangloser Rand, wenn sie keine Ränder gemeinsam haben. Ähnlich sind zwei Subgraphen zusammenhangloser Scheitelpunkt, wenn sie keine Scheitelpunkte (und so, auch keine Ränder) gemeinsam haben. Wenn nicht angegeben, sonst, wie man annimmt, ist eine Reihe zusammenhangloser Subgraphen pairwise zusammenhangloser Scheitelpunkt.

Die Unabhängigkeitszahl α (G) eines Graphen G ist die Größe des größten unabhängigen Satzes von G.

Ein Graph kann in unabhängige Sätze im Sinn zersetzt werden, dass der komplette Scheitelpunkt-Satz des Graphen in zusammenhanglose unabhängige Teilmengen von pairwise verteilt werden kann. Solche unabhängigen Teilmengen werden Partite-Sätze oder einfach Teile genannt.

Ein Graph, der in zwei zweiteilige Partite-Sätze zersetzt werden kann; drei Sätze, dreiteilig; k Sätze, k-partite'; und eine unbekannte Zahl von Sätzen, multipartite. Ein 1-partite Graph ist dasselbe als ein unabhängiger Satz oder ein leerer Graph. Ein 2-partite Graph ist dasselbe als ein zweiteiliger Graph. Wie man auch sagt, ist ein Graph, der in k partite Sätze zersetzt werden kann, k-colourable']].

Ein ganzer multipartite Graph ist ein Graph, in dem Scheitelpunkte angrenzend sind, wenn, und nur wenn sie verschiedenen Partite-Sätzen gehören. Ein ganzer zweiteiliger Graph wird auch einen biclique genannt; wenn seine Partite-Sätze n und M Scheitelpunkte beziehungsweise enthalten, dann wird der Graph K angezeigt.

Ein k-partite Graph ist halbregelmäßig, wenn jeder seiner Partite-Sätze einen gleichförmigen Grad hat; equipartite, wenn jeder Partite-Satz dieselbe Größe hat; und erwogener k-partite, wenn sich jeder Partite-Satz in der Größe durch höchstens 1 mit irgendwelchem anderer unterscheidet.

Die zusammenpassende Zahl eines Graphen G ist die Größe eines größten Zusammenbringens oder pairwise Scheitelpunkt zusammenhanglose Ränder von G.

Ein Überspannen-Zusammenbringen, auch genannt ein vollkommenes Zusammenbringen ist ein Zusammenbringen, das alle Scheitelpunkte eines Graphen bedeckt.

Kompliziertheit

Die Kompliziertheit eines Graphen zeigt die Menge der Information an, dass ein Graph enthalten, und auf mehrere Weisen gemessen werden kann. Zum Beispiel, durch das Zählen der Zahl seiner spinnenden Bäume oder des Werts einer bestimmten Formel, die die Zahl von Scheitelpunkten, Rändern und richtigen Pfaden in einem Graphen einschließt.

Konnektivität

Konnektivität erweitert das Konzept des Angrenzens und ist im Wesentlichen eine Form (und Maß) vom verketteten Angrenzen.

Wenn es möglich ist, einen Pfad von einem Scheitelpunkt bis einen anderen Scheitelpunkt eines Graphen zu gründen, wie man sagt, wird der Graph verbunden; sonst wird der Graph getrennt. Ein Graph wird völlig getrennt, wenn es keinen Pfad gibt, der ein Paar von Scheitelpunkten verbindet. Das ist gerade ein anderer Name, um einen leeren Graphen oder unabhängigen Satz zu beschreiben.

Ein Kürzungsscheitelpunkt oder Aussprache-Punkt, ist ein Scheitelpunkt, dessen Eliminierung den restlichen Subgraphen trennt. Eine Schnittmenge oder Scheitelpunkt geschnitten oder das Trennen des Satzes, ist eine Reihe von Scheitelpunkten, deren Eliminierung den restlichen Subgraphen trennt. Eine Brücke ist ein analoger Rand (sieh unten).

Wenn es immer möglich ist, einen Pfad von einem Scheitelpunkt bis jeder anderen sogar nach dem Entfernen eines k - 1 Scheitelpunkte zu gründen, dann, wie man sagt, ist der Graph k-vertex-connected']] oder k-connected'. Bemerken Sie, dass ein Graph k-connected ist, wenn, und nur wenn es k innerlich enthält, Pfade zwischen irgendwelchen zwei Scheitelpunkten auseinander nehmen. Der Beispiel-Graph wird oben (und deshalb 1-verbunden), aber nicht 2-verbunden verbunden. Die Scheitelpunkt-Konnektivität oder Konnektivität κ (G) eines Graphen G sind die minimale Zahl von Scheitelpunkten, die entfernt werden müssen, um G zu trennen. Der ganze Graph K hat Konnektivität n - 1 für n> 1; und ein getrennter Graph hat Konnektivität 0.

In der Netztheorie ist ein riesiger Bestandteil ein verbundener Subgraph, der eine Mehrheit der Knoten des kompletten Graphen enthält.

Eine Brücke, oder Kürzungsrand oder Landenge, ist ein Rand, dessen Eliminierung einen Graphen trennt. (Zum Beispiel sind alle Ränder in einem Baum Brücken.) Ist ein Trennsatz eine Reihe von Rändern, deren Eliminierung die Zahl von Bestandteilen steigert. Eine Rand-Kürzung ist der Satz aller Ränder, die einen Scheitelpunkt in einer richtigen Scheitelpunkt-Teilmenge S und den anderen Scheitelpunkt in V (G) \S haben. Ränder von K bilden einen Trennsatz, aber nicht eine Rand-Kürzung. Irgendwelche zwei Ränder von K bilden einen minimalen Trennsatz sowie eine Rand-Kürzung. Eine Rand-Kürzung ist notwendigerweise ein Trennsatz; und ein minimaler Trennsatz eines nichtleeren Graphen ist notwendigerweise eine Rand-Kürzung. Ein Band ist ein minimaler (aber nicht notwendigerweise minimal), nichtleerer Satz von Rändern, deren Eliminierung einen Graphen trennt. Ein Kürzungsscheitelpunkt ist ein analoger Scheitelpunkt (sieh oben).

Ein Graph ist k-edge-connected']], wenn ein gebildeter Subgraph durch das Entfernen eines k - 1 Ränder noch verbunden wird. Die Rand-Konnektivität κ' (G) eines Graphen ist G die minimale Zahl von Rändern musste G trennen. Ein wohl bekanntes Ergebnis ist das κ (G) ≤ κ' (G) ≤ δ (G).

Ein Bestandteil ist ein maximal verbundener Subgraph. Ein Block ist irgendein ein maximal 2-verbundener Subgraph, eine Brücke (zusammen mit seinen Scheitelpunkten) oder einem isolierten Scheitelpunkt. Ein biconnected Bestandteil ist ein 2-verbundener Bestandteil.

Ein Aussprache-Punkt (auch bekannt als ein sich trennender Scheitelpunkt) eines Graphen ist ein Scheitelpunkt, dessen Eliminierung vom Graphen seine Zahl von verbundenen Bestandteilen steigert. Ein biconnected Bestandteil kann als ein durch einen maximalen Satz von Knoten veranlasster Subgraph definiert werden, der keinen sich trennenden Scheitelpunkt hat.

Entfernung

Die Entfernung d (u, v) zwischen zwei (nicht notwendig verschieden) Scheitelpunkte u und v in einem Graphen G ist die Länge eines kürzesten Pfads zwischen ihnen. Die Subschrift G ist gewöhnlich fallen gelassen, wenn es keine Gefahr der Verwirrung gibt. Wenn u und v identisch sind, ist ihre Entfernung 0. Wenn u und v von einander unerreichbar sind, wird ihre Entfernung definiert, um Unendlichkeit  zu sein.

Die Seltsamkeit ε (v) eines Scheitelpunkts v in einem Graphen G ist die maximale Entfernung von v bis jeden anderen Scheitelpunkt. Das Diameter diam (G) eines Graphen G ist die maximale Seltsamkeit über alle Scheitelpunkte in einem Graphen; und der Radius rad (G), das Minimum. Wenn es zwei Bestandteile in G, diam (G) und rad (G) definiert gibt, um Unendlichkeit  zu sein. Trivial, diam (G)  2 rad (G). Scheitelpunkte mit der maximalen Seltsamkeit werden peripherische Scheitelpunkte genannt. Scheitelpunkte der minimalen Seltsamkeit bilden das Zentrum. Ein Baum hat höchstens zwei Zentrum-Scheitelpunkte.

Der Wiener Index eines Scheitelpunkts v in einem Graphen G, angezeigt durch W

Die k-th Macht' G eines Graphen G ist ein gebildeter Supergraph durch das Hinzufügen eines Randes zwischen allen Paaren von Scheitelpunkten von G mit der Entfernung am grössten Teil von k. Eine zweite Macht eines Graphen wird auch ein Quadrat genannt.

Ein K-Schraubenschlüssel' ist ein Überspannen-Subgraph, S, in dem alle zwei Scheitelpunkte in den meisten k Malen als weit einzeln auf S sind als auf G. Die Nummer k ist die Ausdehnung. K-Schraubenschlüssel wird verwendet, um geometrische Netzoptimierung zu studieren.

Klasse

Eine Überfahrt ist ein Paar von sich schneidenden Rändern. Ein Graph ist embeddable auf einer Oberfläche, wenn seine Scheitelpunkte und Ränder darauf ohne eine Überfahrt eingeordnet werden können. Die Klasse eines Graphen ist die niedrigste Klasse jeder Oberfläche, auf der der Graph einbetten kann.

Ein planarer Graph ist derjenige, der das (Euklidische) Flugzeug ohne jede Überfahrt angezogen werden kann; und ein Flugzeug-Graph, derjenige, der auf solche Mode gezogen wird. Mit anderen Worten ist ein planarer Graph ein Graph der Klasse 0. Der Beispiel-Graph ist planar; der ganze Graph auf n Scheitelpunkten, für n> 4, ist nicht planar. Außerdem ist ein Baum notwendigerweise ein planarer Graph.

Wenn ein Graph ohne jede Überfahrt gezogen wird, bildet jeder Zyklus, der ein Gebiet ohne irgendwelche Ränder umgibt, die vom Zyklus ins Gebiet reichen, ein Gesicht. Zwei Gesichter auf einem Flugzeug-Graphen sind angrenzend, wenn sie einen allgemeinen Rand teilen. Ein Doppel-, oder planar Doppel-, wenn der Zusammenhang, G eines Flugzeug-Graphen G geklärt werden muss, ist ein Graph, dessen Scheitelpunkte die Gesichter einschließlich jedes outerface G vertreten und in G angrenzend sind, wenn, und nur wenn ihre entsprechenden Gesichter in G angrenzend sind. Der Doppel-von einem planaren Graphen ist immer ein planarer Pseudograph (z.B denken das Doppel-von einem Dreieck). Im vertrauten Fall eines 3-verbundenen einfachen planaren Graphen G (isomorph zu einem konvexen Polyeder P) ist der DoppelG auch ein 3-verbundener einfacher planarer Graph (und isomorph zum Doppelpolyeder P).

Außerdem, da wir einen Sinn "des Inneren" und "draußen" auf einem Flugzeug einsetzen können, können wir ein "äußerstes" Gebiet identifizieren, das den kompletten Graphen enthält, wenn der Graph das komplette Flugzeug nicht bedeckt. Solche Region in äußerster Randlage wird ein Außengesicht genannt. Ein outerplanar Graph ist derjenige, der auf die planare solche Mode gezogen werden kann, dass seine Scheitelpunkte alle neben dem Außengesicht sind; und ein outerplane Graph, derjenige, der auf solche Mode gezogen wird.

Die minimale Zahl von Überfahrten, die erscheinen müssen, wenn ein Graph ein Flugzeug angezogen wird, wird die sich treffende Zahl genannt.

Die minimale Zahl von planaren Graphen musste einen Graphen bedecken ist die Dicke des Graphen.

Belastete Graphen und Netze

Ein belasteter Graph vereinigt ein Etikett (Gewicht) mit jedem Rand im Graphen. Gewichte sind gewöhnlich reelle Zahlen. Sie können auf rationale Zahlen oder ganze Zahlen eingeschränkt werden. Bestimmte Algorithmen verlangen weitere Beschränkungen von Gewichten; zum Beispiel arbeitet der Algorithmus von Dijkstra richtig nur für positive Gewichte. Das Gewicht eines Pfads oder das Gewicht eines Baums in einem belasteten Graphen sind die Summe der Gewichte der ausgewählten Ränder. Manchmal wird ein Nichtrand durch eine spezielle Gewicht-Darstellen-Unendlichkeit etikettiert. Manchmal werden die Wortkosten statt des Gewichts verwendet. Wenn festgesetzt, ohne jede Qualifikation, wie man immer annimmt, ist ein Graph unbelastet. In etwas Schreiben auf der Graph-Theorie ist der Begriff Netz ein Synonym für einen belasteten Graphen. Ein Netz kann geleitet oder ungeleitet werden, es kann spezielle Scheitelpunkte (Knoten), wie Quelle oder Becken enthalten. Die klassischen Netzprobleme schließen ein:

• minimaler Kostenüberspannen-Baum,
• kürzeste Pfade,
• maximaler Fluss (und der Max-Fluss-Lehrsatz des Minute-geschnittenen)

Richtung

Ein geleiteter Kreisbogen oder geleiteter Rand, ist ein befohlenes Paar von endvertices, der grafisch als ein zwischen dem endvertices gezogener Pfeil vertreten werden kann. In solch einem befohlenen Paar wird der erste Scheitelpunkt den anfänglichen Scheitelpunkt oder Schwanz genannt; der zweite wird den Endscheitelpunkt oder Kopf genannt (weil es an der Pfeilspitze erscheint). Ein ungeleiteter Rand ignoriert jeden Orientierungssinn und behandelt beide endvertices austauschbar. Eine Schleife in einem Digraph behält jedoch einen Orientierungssinn und behandelt sowohl Kopf als auch Schwanz identisch. Eine Reihe von Kreisbogen ist vielfach, oder parallel, wenn sie denselben Kopf und denselben Schwanz teilen. Ein Paar von Kreisbogen ist antiparallel, wenn jemandes Kopf/Schwanz der Schwanz/Kopf eines anderen ist. Ein Digraph, oder geleiteter Graph, oder orientierter Graph, ist einem ungeleiteten Graphen analog, außer dass er nur Kreisbogen enthält. Ein Mischgraph kann sowohl geleitete als auch ungeleitete Ränder enthalten; es verallgemeinert sowohl geleitete als auch ungeleitete Graphen. Wenn festgesetzt, ohne jede Qualifikation, wie man fast immer annimmt, ist ein Graph ungeleitet.

Ein Digraph wird einfach genannt, wenn er keine Schleifen und höchstens einen Kreisbogen zwischen einem Paar von Scheitelpunkten hat. Wenn festgesetzt, ohne jede Qualifikation, wie man gewöhnlich annimmt, ist ein Digraph einfach.

In einem Digraph Γ unterscheiden wir Grad d (v), die Zahl von Rändern, einen Scheitelpunkt v, und im Grad d (v), der Zahl von Rändern verlassend, die in einen Scheitelpunkt v eingehen. Wenn der Graph orientiert wird, ist der Grad d (v) eines Scheitelpunkts v der Summe von seinem - und in - Grade gleich. Wenn der Zusammenhang klar ist, kann die Subschrift Γ fallen gelassen sein. Maximum und Minimum Grade werden durch Δ (Γ angezeigt) und δ (Γ); und Maximum und Minimum in Graden, Δ (Γ) und δ (Γ).

Eine-Nachbarschaft oder Nachfolger ist untergegangen, N (v) eines Scheitelpunkts ist v der Satz von Köpfen von Kreisbogen, die von v gehen. Ebenfalls ist ein in der Nachbarschaft, oder Vorgänger untergegangen, N (v) eines Scheitelpunkts ist v der Satz von Schwänzen von Kreisbogen, die v eintreten.

Eine Quelle ist ein Scheitelpunkt mit 0 im Grad; und ein Becken, 0-Grad.

Ein Scheitelpunkt v beherrscht einen anderen Scheitelpunkt u, wenn es einen Kreisbogen von v bis u gibt. Eine Scheitelpunkt-Teilmenge S herrscht vor, wenn jeder Scheitelpunkt nicht in S durch einen Scheitelpunkt in S beherrscht wird; und im Beherrschen wenn jeder Scheitelpunkt in S durch einen Scheitelpunkt nicht in S beherrscht wird.

Ein Kern in einem Graphen G ist ein unabhängiger Satz S, so dass (G \S) ein vorherrschender Satz ist. Ein Digraph ist vollkommener Kern, wenn jeder veranlasste Subdigraph einen Kern hat.

Ein Eulerian Digraph ist ein Digraph mit dem gleichen in - und-Grade an jedem Scheitelpunkt.

Der zweieck eines ungeleiteten Randes ist das Paar von diedges

und die den einfachen dicircuit bilden.

Eine Orientierung ist eine Anweisung von Richtungen zu den Rändern eines ungeleiteten oder teilweise geleiteten Graphen. Wenn festgesetzt, ohne jede Qualifikation wird es gewöhnlich angenommen, dass alle ungeleiteten Ränder durch einen geleiteten in einer Orientierung ersetzt werden. Außerdem, wie man gewöhnlich annimmt, ist der zu Grunde liegende Graph ungeleitet und einfach.

Ein Turnier ist ein Digraph, in dem jedes Paar von Scheitelpunkten durch genau einen Kreisbogen verbunden wird. Mit anderen Worten ist es ein orientierter ganzer Graph.

Ein geleiteter Pfad, oder gerade ein Pfad, wenn der Zusammenhang klar ist, ist ein orientierter einfacher solcher Pfad, dass alle Kreisbogen dieselbe Richtung gehen, bedeutend, dass alle inneren Scheitelpunkte in - und-Grade 1 haben. Ein Scheitelpunkt v ist von einem anderen Scheitelpunkt u erreichbar, wenn es einen geleiteten Pfad gibt, der von u und Enden an v anfängt. Bemerken Sie, dass im Allgemeinen die Bedingung, dass u von v erreichbar ist, nicht andeutet, dass v auch von u erreichbar ist.

Wenn v von u erreichbar ist, dann ist u ein Vorgänger von v, und v ist ein Nachfolger von u. Wenn es einen Kreisbogen von u bis v gibt, dann ist u ein direkter Vorgänger von v, und v ist ein direkter Nachfolger von u.

Ein Digraph wird stark verbunden, wenn jeder Scheitelpunkt von jedem anderen im Anschluss an die Richtungen der Kreisbogen erreichbar ist. Im Gegenteil wird ein Digraph schwach verbunden, wenn sein zu Grunde liegender ungeleiteter Graph verbunden wird. Von einem schwach verbundenen Graphen kann als ein Digraph gedacht werden, in dem jeder Scheitelpunkt von jeder ander, aber nicht notwendigerweise im Anschluss an die Richtungen der Kreisbogen "erreichbar" ist. Eine starke Orientierung ist eine Orientierung, die einen stark verbundenen Digraph erzeugt.

Ein geleiteter Zyklus, oder gerade ein Zyklus, wenn der Zusammenhang klar ist, ist ein orientierter einfacher solcher Zyklus, dass alle Kreisbogen dieselbe Richtung gehen, bedeutend, dass alle Scheitelpunkte in - und-Grade 1 haben. Ein Digraph ist acyclic, wenn es keinen geleiteten Zyklus enthält. Ein begrenzter, acyclic Digraph ohne isolierte Scheitelpunkte enthält notwendigerweise mindestens eine Quelle und mindestens ein Becken.

Ein arborescence, oder-Baum oder das Ausbreiten, ist ein orientierter Baum, in dem alle Scheitelpunkte von einem einzelnen Scheitelpunkt erreichbar sind. Ebenfalls ist ein im Baum ein orientierter Baum, in dem ein einzelner Scheitelpunkt von jedem anderen erreichbar ist.

Geleitete acyclic Graphen

Die teilweise Ordnungsstruktur von geleiteten acyclic Graphen (oder DAGs) gibt ihnen ihre eigene Fachsprache.

Wenn es einen geleiteten Rand von u bis v gibt, dann sagen wir, dass u ein Elternteil von v ist und v ein Kind von u ist. Wenn es einen geleiteten Pfad von u bis v gibt, sagen wir, dass u ein Vorfahr von v ist und v ein Nachkomme von u ist.

Der moralische Graph eines DAG ist der ungeleitete geschaffene Graph durch das Hinzufügen eines (ungeleiteten) Randes zwischen allen Eltern desselben Knotens (manchmal genannt Verbindung), und dann das Ersetzen aller geleiteten Ränder durch ungeleitete Ränder. Ein DAG ist vollkommen, wenn, für jeden Knoten, der Satz von Eltern abgeschlossen ist (d. h. keine neuen Ränder hinzugefügt werden müssen, wenn man den moralischen Graphen bildet).

Das Färben

Scheitelpunkte in Graphen können Farben gegeben werden, um sie zu identifizieren oder zu etikettieren. Obwohl sie wirklich in Diagrammen in verschiedenen Farben, Arbeitsmathematiker allgemein Bleistift in Zahlen oder Briefen (gewöhnlich Zahlen) gemacht werden können, um die Farben zu vertreten.

In Anbetracht eines Graphen G (V E) ist ein K-Färben' von G eine Karte ϕ: V  {1..., k} mit dem Eigentum dass (u, v)  E  ϕ (u)  ϕ (v) - mit anderen Worten, wird jeder Scheitelpunkt eine Farbe mit der Bedingung zugeteilt, dass angrenzende Scheitelpunkte dieselbe Farbe nicht zugeteilt werden können.

Die chromatische Zahl χ (G) ist der kleinste k, für den G ein K-Färben hat.

In Anbetracht eines Graphen und eines Färbens sind die Farbenklassen des Graphen die Sätze von Scheitelpunkten gegeben dieselbe Farbe.

Verschieden

Ein Graph invariant ist ein Eigentum eines Graphen G, gewöhnlich eine Zahl oder ein Polynom, das nur von der Isomorphismus-Klasse von G abhängt. Beispiele sind die Ordnung, die Klasse, die chromatische Zahl und das chromatische Polynom eines Graphen.

Siehe auch

• Graph (Mathematik)
• Liste von Graph-Theorie-Themen
• Graph-Triangulation, Jayson Rome, am 14. Oktober 2002

http://prl.cs.gc.cuny.edu/web/LabWebsite/Rome/jrome/Slides_Tutorials/GraphTriangulation.pdf

• Bollobás, Béla (1998). Moderne Graph-Theorie. New York: Springer-Verlag. Internationale Standardbuchnummer 0-387-98488-7. [Gepackt mit fortgeschrittenen Themen, die von einer historischen Übersicht am Ende jedes Kapitels gefolgt sind.]
• [Standardlehrbuch, grundlegendstes Material und einige tiefere Ergebnisse, Übungen der verschiedenen Schwierigkeit und Zeichen am Ende jedes Kapitels; bekannt, um fehlerfrei zu sein Quasi-. Freie elektronische Version ist verfügbar.]
• Westen, Douglas B. (2001). Einführung in die Graph-Theorie (2ed). Oberer Sattel-Fluss: Prentice Hall. Internationale Standardbuchnummer 0-13-014400-2. [Tonnen von Illustrationen, Verweisungen und Übungen. Das am meisten ganze einleitende Handbuch zum Thema.]
• Zaslavsky, Thomas. Wörterverzeichnis von unterzeichneten und Gewinn-Graphen und verbundenen Gebieten. Elektronische Zeitung von Combinatorics, Dynamische Überblicke in Combinatorics, # DS 8. http://www.combinatorics.org/Surveys /