Glossar vo da Graphntheorie

Des **Glossar vo da Graphntheorie** enthoit a Stichwortvazeichnis und kuaze Definitiona und Omeakunga zu de wichtigstn Begriffe vo da Graphntheorie

### Schlisslbegriff
* **Knupf (Knopf)**, engl. vertex, dt. Knoten
* **Vabinda**, engl. edge, dt. Kante 
* **Haffa (Haufn)**, engl. set, dt. Menge  
* **Haffaleah (Haufnleah)**, engl. set theory, dt. Mengenlehre

## A

### Achromatische Zoi

:De achromatische Zoi \psi (G) vo am Graphn G is de gresste Zoi k, fia de G a gitige und voistendige Knupffeabung mit k Forbm hod.

:*Schau aaa:* chromatische Zoi, pseudo-achromatische Zoi.

### Adjazenz

:**Adjazenz** is a Beziahung zwischn Knupf oda Vabind in am ungrichtetn Graphn. Zwoa Knupf hoassn **adjazent** oda **benochboart**, wenn se in demsejm duach a Kantn vabundn san. Zwoa Kantn hoassn **adjazent** oda **benochbort**, wann sa si in am Knupf berian, des hoasst an Knupf gmoasam besitzen.

:*Schau aaa:* Inzidenz, Adjazenzmatrix.

### Adjazenzlistn

:A **Adjazenzlistn** is a Meglichkeit, Graphn im Rechna dorzstejn. Dabei wead zu jedm Knupf a Listn vo seine Nachborn gfiat. Dazua wead z.&nbsp;B. a vakettete Listn oda a Fejd (Array) vawendt.

:*Schau aaa:* Adjazenzmatrix.

### Adjazenzmatrix

: A **Adjazenzmatrix** is a binäre Matrix, wo olle Knupf enthoid und jeweis de Eareichborkeit zum direktn Nochfoiga markiat. Addiat mit da Einheitsmatrix ergibt si de Erreichborkeitsmatrix im easchtn Schritt.

### Adjazenzram

:Da **Adjazenzram** vo am Graphn is da Vektorram, wo vo de Spoitn vo da Adjazenzmatrix afgspannt wead.
:De Adjazenzram vo isomorphn Graphn san isomorphe Ram.

### Alternierenda Pfad

:*Schaug:* Vabesserungspfad.

### Artikulation

:A trennende Knupfmenge, wo aus amKnupf besteht, wead **Artikulation** gnennt.

### Augmentierender Pfad

:*Schaug:* Vabesserungspfad.

### Ausgangsgrad

:Ois **Ausgangsgrad** vo am Knupf wead in am grichtetn Graphn de Ozoi vo seine sdirektn Nochfoiga bezeichnet. Ma nennt des aa ois an positivn Gran vo am Knupf.

:*Schau aaa:* Grad, Eingangsgrad.

### Ausgangsmenge

:Ois **Ausgangsmenge** vo am Knupf wead in am grichtetn Grapnh de Menge vo seim direktn Nochfoiga bezeichnet.

### Automorphismus

:A **Automorphismus** vo am Graphn is a Permutation vo de Knupf, ba de zwoa Knupf genau dann duach a Kantn vabundn san, wenns de Buida vo de boadn Knupf san.

### Azyklischa Graph

:A **azyklischa Graph** is a grichteta Graph, wo koan Zyklus enthoit.

## B
*[[#top|(zum Seitenofong)]]*

### Bandbroadn

:De **Bandbroadn** (engl. bandwidth, schaug aa Bandbroadn) vo am endlichn, schlichtn, ungrichtetn Graphn is wia foigt definiat: Sei L: V \to\{1,\ldots,n\} a eineindeitige Nummariarung vo de Knupf. Dann bezeichnet \max_{\{i,j\}\in E} |L(i)-L(j)| de **Bandbroadn in Bezug af <math>L</math>** und \min_L \max_{\{i,j\}\in E} |L(i)-L(j)| de **Bandbroadn** vom Graphn (V,E).
:De Eamiddlung vo da Bandweitn is oans vo de wenign Probleme, wo aa fia Baam NP-voiständig is.

### Baam

:A **Baam** is a zammahängenda Graph, wo koane Zykln enthoit. Genaua: *<math>G</math> is maximal kroasfrei und minimal zammahängend.* D. h. koa Kantn ko zua Kantnmenge dazuafigt wean, ohne oan Kroas z eazeign, und koane ko entfeant wean, ohne de Zammeahangs-Eigenschoaft z valetzn.

:*Haptartikl*: Baam.

### Baamkantn

:*Schaug:* Vorweatsvabinda.

### Bipartition

:A **Bipartition** is a 2-Partition.

### Bipartita Graph

:A **bipartita Graph** is a oafocha Graph, wo a Bipartition besitzt.
:Nochm Dénes Kőnig is a Graph genau dann bipartit, wann a koan Kroas vo ungroda Läng besitzt.

### Blatt

:A **Blatt** is a Knupf in am Baam wo nua oan Nochborn hod. In am Wuazlbaam muass a Blatt zuasätzle varschiedn zua Wuazl sein. Da eindeitige Nochbor is dann da Vorgänga, und a Blatt hod koan Nochfoiga.

### Block

:A **Block** B vo am Graphn G is a Teigraph, wo maximal in dera Oagnschoft is, dass a zwoafoch knupfzammahängend is. Des hoasst, dass wenn a weidane Knupf vo G zu B dazuakematn, dea zua oam vo de ondan Knupf vo B nua oan Weg häd.

### Blockgraph

:An Blockgraph block(G) zu oam Graphn G eafuit de foigendn Oagnschoftn:
:* Fia jedn Schnittknupf in G gibts genau oan Knupf in block(G).
:* Fia jedn Block in G gibts genau oan Knupf in block(G).
:* Kantn valaffa zwischn Schnittknupf und Blockknupf genau dann, wann da Block an Schnittknupf enthoid.
:* Es gibt koane weidan Knupf und Kantn in block(G).

### Bogn

:*Schaug:* Grichtete Kantn.

### Bruggn

:A Kantn k hoasst **Bruggn** in an Graphn G, fois zwoa Knupf x, y in G existian, fia de jeda Weg vo x noch y iwa k fiat. Äquivalent losst si a Bruggn ois Kantn charakterisian, wo af koam Kroas in G liegt.

## C
*[[#top|(zum Seitnofang)]]*

### Chordala Graph

:*Schaug:* Trianguliata Graph.

### Chromatische Zoi

:De **chromatische Zoi** (aa **Knupffeabungszoi** oda kuaz **Feabungszoi**, sejtn aa **Forbzoi** gnennt) vo am Graphn is de kloanste Zoi k, fia de da Graph ae zualässige Knupffearbung mit k Forbm besitzt. Des is gleizeiti as de kloanste natialiche Zoi, fia de des chromatische Polynom \chi(G,\lambda)\neq 0 is.

:*Schau aaa:* Partition, Feabung, achromatische Zoi, pseudo-achromatische Zoi.

### Chromatischa Index

:Da **chromatische Index** (aah **Kantnfeabungszoi**) vo am Graphn is de kloanste Zoi k, fia de da Graph a zualässige Kantnfeabung mit k Forbm besitzt.

:*Schau aaa:* Feabung.

### Clique
:A **Clique** is in am ungrichtetn Graphn a Teimenge vo de Knupf, innahoib vo dena olle Knupf poarweis mit oana Kantn vabundn san.

### Cliquenproblem

:Des **Cliquenproblem** frogt, zua am gegebanen ungrichtetn Graphn G und oana natialichn Zoi k, ob de Cliquenzoi vo G mindastns so gross wia k is.

### Cliquenzoi

:De **Cliquenzoi** \omega (G) vo am ungrichtetn Graphn G is de gresste Zoi k, für de G eine Clique der Größe k besitzt.

:*Schau aaa:* Cliquenproblem.

## D
*[[#top|(zum Seitenofong)]]*

### Diafn

:De *Diafn* vo am Knupf in am Wuazlbaam is de Onzoi vo Kantn im Weg vo da Wuazl bis zum Knupf.

:*Schau aaa:* Heh.

### Dichtn

:De **Dichtn** dn(G) vo am oafochn Graphn G=(V, E) is des Vahejtnis vo seina Vabindazoi zua Vabindazoi vo am voiständign Graphn af gleichvui Knupf, des hoasst:
:::dn(G)=\frac{2|E|}{|V|(|V|-1)}.

### Digraph

:*Schaug:* grichteta Graph.

### Dilation

:De **Dilation** vo am euklidischn Graphn is a Moß dafia, wiavui Umweg ban Duachlaffn vom Graphn in Kauf gnomma wean muass, im Vagleich zua direktn euklidischn Streckn.

: *Schau aaa:* Dilation.

### Direkta Nachfoiga

:In am grichteten Graphn hoasst a Knupf v **direkta Nochfoiga** vo am Knupf u fois s a Kantn gibt, wo vo u noch v ged.

### Direkta Voagänga

:In am grichteten Graphn hoasst a Knupf u **direkta Voagänga** vo am Knupf v fois s genau a Kantn u,v gibt, wo noch v ged.

### Disjunkte Weg

:Zwoa Weg v=(v_1, v_2, \ldots, v_p) und w=(w_1, w_2, \ldots, w_q) hoassn **disjunkt**, fois olle Knupf aus v vaschiedn vo dena aus w san. Haifig losst ma zua, dass v_1=w_1 und v_p=w_q, oisdann dass s Weg vom gleichn Startknupf zum gleichn Zuiknupf san. A Menge vo Wegn hoasst **disjunkt**, wanns poarweis disjunkt san.
:Existiarn fia jeds Poar x,y vo Knupf p disjunkte Weg vo x noch y, so nennt ma an Graphn ''p''-foch knupfzammahängend.

### Distanz

:De **Distanz** vo zwoa Knupf v und w in am Graphn (aa **Obstand** vo de Knupf gnennt) is de Läng vo am kiazestn Pfad, wo vo v noch w fiat. Fois a soichana Pfad ned existiat, so wead da Obstand af unendli (\infty) gsetzt. Da Obstand vo am Knupf zu si sejm is (0).

### Distanzgraph

:A Distanzgraph D_G vo am Graphn G=(V, E) is da voiständige kantngwichtetn Graphn iwa V, wo jeda Kantn de Distanz vo de zuaghearign Knupf in G zuaordnet.

### Dominationszoi

:De **Dominationszoi** \gamma (G) is de Mächtigkeit vo oana kloanstn dominiarendn Knupfmenge vo G.

### Dominiarende Knupfmenge

:A Knupfteimenge X\subseteq V vo am Graphn G=(V, E) hoasst **dominiarend**, wann jeda Knupf aus V\setminus X zu am Knupf aus X adjazent is.

### Dreieck

:A **Dreieck** is a Graph mit drei Knupf, wo olle zuaeinanda adjazent (benachbort) san.

### Dreiecksfreia Graph

:A **dreiecksfreia Graph** is oana, wo koan Kroas vo da Läng 3 (a Dreieck) ois Teigraph hod.

### Duala Graph

:G=(V, E) is a planara Graph mit oana gegebenen planarn Einbettung. Da **duale Graph** G^*=(V^*, E^*)\! entsted aus G, indem jeda Flächn vo G a Knupf vo G^* zuagordnet wead. Zwoa Knupf aus G^* wean duach k Kantn vabunden, wann de entsprechendn Flächn aus G genau k gmoasame Randkantn besitzn.
:Omeakung: Fia zammahängende G guit: G** = G, des hoasst: Da duale Graph voms dualn Graphn is da Graph sejm.

### Duachmessa

:Da **Duachmessa** D(G) vo am Graphn G is des Maximum vo de Exzentrizitätn vo de Knupf vo G
:Fia olle Graphn G guit R(G)\le D(G) \le 2 \cdot R(G). Dabei is R(G) da Radius vo G.

:*Schau aaa:* Zentrum.

## E
*[[#top|(zum Seitenofong)]]*

### Eckn

:*Schaug:* Knupf.

### Einbettung

:A Doarstellung vo am Graphn in da Ebene wead ois **Einbettung** bezeichnet. Is de Doarstejlung iwakreizungsfrei, so red ma vo oana *planarn Einbettung*.

### Eingangsgrad

:Da **Eingangsgrad** vo am Knupf is in am grichtetn Graphn de Ozoi vo seine direktn Vorgänga bezeichnet. Ma nennt des aa an negativn Grad vo am Knupf.

:*Schau aaa* Grad, Ausgangsgrad, Nochborschoft und Grad in Graphn.

### Eingangsmenge

:De **Eingangsmenge** vo am Knupf is in am grichtetn Graphm de Menge vo seine direktn Vorgänga.

### Endknupf vo oana Kantn

:Is k=(x,y) a gerichtete Kantn, so bezeichnet ma x ois ian Startknupf und y ois ian **Endknupf**.
:Ba ungrichtetn Vabinda k=\{x,y\} ko ma x und y sowoi ois Startknupf ois aa ois Endknupf bezeichnen. Do red ma in da Regl owa oafoch vo dena boadn  „zu k inzidentn Knupf“.

### Eareichborkeitsmatrix

:De **Eareichborkeitsmatrix** is a binäre Matrix und gibt im n-tn Schritt de gsamte Eareichborkeit vo de Knupf untereinanda o.
:Da 1. Schritt entsteht duach de Addition vo da Oaheitsmatrix mit da Adjazenzmatrix. Da naxte Schritt is imma de Anfangsmatrix multipliziat mit da voaherign Matrix oda zum Beispui da 3. Schritt multipliziat mitm 2. Schritt eagibt an 5. Schritt. Tritt koa Vaenderung zum jeweilign naxstn Schritt ei, bricht da Algorithmus ob.

### Euklidisches Traveling-Salesman-Problem

:Des **Euklidische Travelling Salesman Problem** is des Travelling Salesman Problem fia oan kantnbewertetn Graphn, in dem de Dreiecksungleichung guit.

:*Schau aaa:* Problem vom Handlungsreisendn.

### Eulerkroas

:Da Begriff **Eulerkroas** wead synonym fia Eulertour vawendet. De Bezeichnung „Eulerkroas“ is insofean foisch, wei s si im Oigmoanan ned um oan Kroas, sondan um oan Zyklus handet.

### Eulerscher Graph

:A **eulerscher Graph** is a Graph, wo a Zyklus existiat, dea jede Kantn genau oamoi enthoid.
**Leonhard Euler hod 1736 zoagt, dass in jedn Eulerschen Graphn olle Knupf an grodn Grad hom, weshoib Eulersche Graphn noch eam benannt san. Ea hod emfois zoagt, dass in jedn semieulerschen Graphe entweda koa oda zwoa Knupf ungrodn Grad hom. Auf de Weisn lest a des Königsberger Bruggnproblem.
**Carl Hierholzer hod 1873 de Umkearung zoagt, dass in jedn zammahängendn Graphn, in dem jeda Knupf an grodn Grad hod, a Eulertour existiat und in jedn Graphn, in dem zwoa Knupf ungrodn Grad hom, a Eulerweg existiat.

:*Schau aaa:* Eulerkroasproblem.

### Eulertour

:A **Eulertour** is a Zyklus, wo iwa olle Kantn vo am Graphn lafft.

### Eulerweg

:A **Eulerweg** is a Weg,  wo iwa olle Kantn vo am Graphn lafft.

### Eulerzug

:A gschlossena Vabindazug in am Graphn hoasst **Eulerzug**, wann a jede Kantn vom Graphn genau amoi enthoit. A Graph hoasst **eulersch**, wann a oan soichn Kantnzug besitzt.

:*Schau aaa:* Eulerscher Graph.

### Exzentrizität

:De **Exzentrizität** e(x) vo am Knupf x is de Distanz (de Läng vo am kiazestn Weg) zu am Knupf y, wo maximaln Obstand vo x hod.

:*Schau aaa:* Radius, Duachmessa, Zentrum.

## F
*[[#top|(zum Seitenofong)]]*

### Feabung

:*Schaug:* Knupffeabung, Kantnfeabung.

### Feabungszoi

:*Schaug:* Chromatische Zoi.

### Faktor

:Is G=(V, E) a Graph und g a Obbuidung vo de Knupf af natialiche Zoin, so is an **<math>g</math>-Faktor** F a Teigraph vo G, mit V(F) = V(G) (oiso nur Kantn wean entfernt) und jeda Knupf x hod in F an Grad g(x).

:Is g(x) = p fia olle Knupf x, so red ma aa vo am p-Faktor.
:Is g(x) \ge a und g(x) \le b fia olle Knupf x, so red ma vo am [a,b]-Faktor.

**A Poarung is a [0,1]-Faktor; a perfekte Poarung is a 1-Faktor; Hamiltonsche Graphn besitzen oan 2-Faktor.
**Da **1-Faktorsatz vo Tutte** besogt, dass ma aus G und g oan Graphn G^* konstruian ko, wo genau dann oan 1-Faktor besitzt, wann G oan g-Faktor besitzt. Des is de Definition vo oana Reduktion im Sinn vo da theoretischen Informatik. Wei umgekeat 1-Faktorn Spezialfoi vo g-Faktorn san, is des g-Faktorproblem äquivalent zum 1-Faktorproblem.

### Faktor-kritisch

:A Graph G mit G\neq \emptyset hoasst **faktor-kritisch**, wann duach des Wegganehma vo am Knupf a perfekte Poarung megli wead.

### Fobzoi

:*Schaug:* Chromatische Zoi.

### Flächn

:**Flächn** vo am planarn Graphen nennt man des Gebiet vo da Ebene (oda vo oana Flächn in \mathbb{R}^3), wo duach a Kantn vo am planarn Graphn, dea wo in da Ebene (bzw. auf da Flächn) einbedd is, eigrahmt wead.

### Fluss

:A **Fluss** zu am grichtetn Graphn und Kantnkapazitetn it a Funktion f vo de grichtetn Kantn af de nednegativn reelln Zoin. An Fluss deaf jeda Kantn nur oan Wert zuaweisn, wo hextns so gross is wia de Kapazitet vo dera Kantn.
:Redd ma vo am *s-t-Fluss*', muass feana fiar jedn Knupf x (aussa fia de Quejn s und de Senkn t) gejtn, dass de Summe vo de Flisse af de einefiarendn Kantn gleich da Summe vo de Flisse af de aussefiarendn Kantn is.
::*Formal*: \forall x\in V\setminus \{ s,t \} : \sum_{e\in \delta^-(x)}f(e) = \sum_{e\in \delta^+(x)}f(e)
::*Anschaulich*: aus koam Knupf (aussa s und t) meara aussefliassn ois einefliasst und ois, wos in an Knupf einefliasst, fliasst aa wieda ausse.

### Fundamentalkroas
Zu am afspannendn Baam T hoasst W *[[#Kreis|Kroas]]*, fois a duach Dazuadoa vo oana Kantn zum Baam dazeigt wead.

### Fundamentalschnitt
Wann G zammahengend is. Zu am Spannendn Baam T hoasst S *[[#Schnitt|schnitt]]*, fois S ois Knupfmenge duach Weggalossa vo oana Kantn im Baam ois Zammahangskomponentn entsteht.

## G
*[[#top|(zum Seitenofong)]]*

### Gordneta Baam

:A gordneta Baam it a Wuazelbaam, wo fia de Kinda vo jedn Knupf a Ordnungsrelation definiat is. De Ordnung legt fest, wia de Nochfoiga vo am Knupf in da grafischn Dorstejung vo am Baam ozoagt wean (z. B. vo links noch rechts nochm Ordnungskriterium). Formal wead duach de Ordnung festglegt, in wejcha Reihnfoige de Knupfn ba untaschiedlichn Traversiarungsvafoan (preorder, inorder, postorder) duachlaffa wean.

### Grichteta Graph

:A **Grichteta Graph** (aa **Digraph** gnennt) is a Graph, wo grichtete Vabinda enthoit.

:*Schau aaa:* Typn vo Graphn in da Graphntheorie.

### Grichtete Kantn
:A **grichtete Kantn**, aa **Bogn** oda **Pfei** gnennt, vabindet zwoa Knupf vo am Graphn unta Beochtung vo oana Reihnfoige. A grichtete Kantn wead dahea ois gordnetes Poar vo zwoa Knupf notiat.

:*Schau aaa:* Ungrichtete Kantn, Typn vo Graphn in da Graphntheorie.

### Grichteta Kroas
:*Schaug:* Grichteta Zyklus.

### Grist
:A Grist is a Teigraph vo am Graphn G = (V, E), wo olle Knupf aus V enthoit. Is G zammahengend, so is des Grist zglei a Spannbaam. Is G ned zammahengend, so bezeichnet ma des entstehende Grist aa ois *Spannwoid* oda *afspannenda Woid*.

### Gwicht

:Des **Gwicht** is a reelle Zoi, wo am Knupf oda oana Kantn zuagordnet wead.

### Grad

:Da **Grad** vo am Knupf in am ungrichtetn Graphn (aa **Valenz** gnennt) is de Ozoi vo seine Nochban.

### Gradfoige

:Ois Gradfoige vo am Graphn G = (V, E) mit dena Knupf v_1, v_2, \ldots, v_n \in V bezeichnet ma de Foige natialicha Zoin d_1, d_2, \ldots, d_n, wejche jeweil an Grad vo oanzalnen Knupf ogem, d. h. deg(v_i) = d_i fia olle i = 1, 2, \dots, n. A soichane Foige vo natialichn Zoin hoasst a **graphisch**, wann echt mindastns oa Graph existiat, wo de Gradfoige hod.

### Graph

:A **Graph** is a Tupl (V, E). V is a nedlaare Menge vo Knupf, E a Menge vo Kantn.

:Jede Kantn hod je oan Ofangs- und Endknupf. Wean Ofangs- und Endknupf ned untaschieden, redd ma vo am ungrichtetn Graphn, andanfois vo am grichtetn Graphn. In am Graphn ohne Meafochkantn is jede Kantn scho duach des Poar aus Ofangs- und Endeckn bestimmt.

### Graphisch

:Ois **graphisch** bezeichnet ma a Foige natialicha Zoin, wo de Gradfoign vo am Graphn is.

### Graph mit Meahfochvabinda

:Wead de Fordarung aufgem, dass a Kantn duach iare zwoa Knupf festglegt is, so kenna zwoa Knupf aa duach meah ois a Kantn miteinanda vabundn sein. In dem Foi redd ma vo **Meahfochkantn**.

### Gresste Clique

:*Schaug:* Maximale Clique.

### Gresste Poarung

:*Schaug:* Maximale Poarung.

### Gresstes Matching

:*Schaug:* Maximale Poarung.

### Grossvodda

:Untam **Grossvodda** vo am Knupf v inam grichtetn Baam vasteht man an Vodda vom Vodda vo v.

### Gitige Feabung

:*Schaug:* Gitige Knupffeabung.

### Gitige Kantnfeabung

:A Kantnfeabung is **gitig** (oda **echt**), fois koane inzidentn Kantn existian, wo mit da gleichn Foab gfeabt san.

### Guitige Knupffeabung

:A Knupffeabung is **gitig** (oda **echt**), fois koa adjazentn Knupf existian, wo mit da gleichn Foab gfeabt san.

## H
*[[#top|(zum Seitenofong)]]*

### Hamiltonobschluss

:Da **Hamiltonabschluss** (oda Huin; n-Huin) vo am Graphn G=(V, E) is da Obagraph (oda Supagraph) vo G mit identischa Knupfmenge und zuasatzli iterativ einbautn Kantn, wo ned-adjazente (oda ned-benochboarte; ned-vabundene) Knupf mit Gradsumme \geq n=|V| miteinanda vabindn, so lang des meglich is. Da Hamiltonobschluss vo am Graphn is eindeitig.

### Hamiltonscha Graph

:A Graph hoasst **hamiltonsch**, fois a oan Hamiltonkroas besitzt.

### Hamiltonkroas

:A **Hamiltonkroas** is a Kroas, wo olle Knupf vo am Graphn enthoit.

### Hamiltonkroas Problem

:Des Hamiltonkroas Problem is de Frog danoch, ob an gegebena Graph oan Hamiltonkroas besitzt. Des Problem is im oigmoanan NP-voistendig.
:Fir oanige Graphnklassn is des Problem owa polynomial leesbor. Schaug dazua Hamiltonkroasproblem

### Hamiltonpfad

:An **Hamiltonpfad** is a Pfad, wo olle Knupf vom Graphn enthoit.

### Handschlag-Lemma

:Des **Handschlag-Lemma** sogt, dass de Summe vo Knupfgrad glei 2 \cdot |E(G)| is. (Jede Kantn drogt ba genau zwoa Knupf zum Knupfgrad bei.) Daraus foigt, dass de Summe vo de Knupfgrade stets grod is. Bsundas gibts imma a grode Ozoi vo Knupf, de ungrodn Grad hom.

### Hehn

:De **Hehn** vo am Wuazlbaam is de maximal aftretende Tiafn.

### Homöomorphie

:Zwoa Graphn hoassn **homöomorph**, fois se isomorph san oda an gmoasaman Untarteilungsgraphen hom. Zwoa Graphen san genau dann homöomorph, wann eanare Homöomorphie-Urspriüng isomorph san. Oschaulich bedeidd des, dass zwoa homöomorphe Graphn aus am gemoasamen Ursprungsgraphn duach Einfiagn vo neien Knupf vom Grad 2 in scho existiarendn Kantn heavoagenga.

:*Schau aaa:* Planara Graph.

### Homeomorphie-Uasprung

:Da **Homeomorphie-Uasprung** HU(G) vo am Graphn G=(V, E) is da kloanste Graph, zu dem G homeomorph is. Ma berechnet HU(G) mit am foigenden Algorithmus:
:#Fois G koan Knupf vom Grad 2 besitzt (obgsegn vo isoliatn Knupf wo nua a Schleifn besitzen) so is HU(G)=G.
:#Wej oan Knupf x vom Grad 2 (aussa isoliate Knupf mit oana Schleifn) mit dena boadn Nachborn y und z (aa y=z is meglich)
:#Entfean x, dua dafia a Kantn vo y noch z dazua.Formal: G \leftarrow (V\setminus \{x\},E\cup \{\{y,z\}\})
:#geh zu 1

:*Schau aaa:* Planara Graph.

### Hozadssotz

:In bipartiten Graphen G mit Bipartition \{A,B\} existiad genau dann eine Paarung M der Kardinalität |M| = |A| (de jeden Knupf aus A überdeckt), falls für jede Teilmenge S von A gilt, dass ihre Nachbarschaft mindestens so groß ist wie S selbst:
:|N(S)| \ge |S|,\  \forall S\subseteq A

:*Siehe auch:* Paarung.

### Hypergraph

:Ois **Hypergraph** wean Graphn bezeichnet, bei dena Vabinda mea wia nur zwoa Knupf vabindn kenna. Kantn vo dera Foam nennt ma gwehnlich Hyperkantn. Mengentheoretisch betrochtet san Hypergraphen dessejbe wia Mengensysteme.

:*Schau aaa:* Typn vo Graphn in da Graphtheorie.

### Hyperkantn

:Ois **Hyperkantn** wean Kantn in Hypergraphn bezeichnet. De kenna duatn mea wia zwoa Knupf miteinanda vabindn.

:*Schau aaa:* Typn vo Graphn in da Graphtheorie.

### Hypohamiltonsch

:A Graph G hoasst **hypohamiltonsch**, wanna koan hamiltonschn Kroas besitzt, owa zu jedn vo seine Knupf a Kroas existiat, wo olle andan Knupf enthoit.

## I
*[[#top|(zum Seitenofong)]]*

### Index
:Da **Index** vo am Graphn is definiat ois:

:\mu (G):=|E(G)|-|V(G)|+\kappa (G) (Ozoi vo de Kantn − Ozoi vo de Knupf + Ozoi vo de Zammahangskomponentn)
**Fia olle Graphn G is \mu (G) \ge 0 und G is genau dann a Woid, wann \mu (G) = 0 guit
**Da Index vo am Graphn G is stets kloanagleich da Ozoi vo seine Kroas und G is genau dann a Kaktusgraph, wann sein Index da Ozoi vo de Kroas in G entspricht

### Induziata Teigraph

:Is G a Graph und I\subseteq V(G) Teimenge vo da Knupfmenge vo G, so is da vo I **induziate Teigraph** a Teigraph, wo duach de Entfeanung vo de Knupf aus G entsteht, wo ned in I liagn (miakts enk: bei Entfeanen vo am Knupf k foin aa olle mit k inzidentn Kantn wegga).
:Anschaulich bedeidd des: Dea vo I induziate Teigraph besteht aus dena Knupf aus I und oin Kantn, wo in G zwischn eana valaffa.

:Formal: dea vo I induziate Teigraph is G-(V(G)\setminus I)

### Innara Knupf

:A Knupf in am Graphn wead **innara Knupf** gnennt, wanns a si bei dem Knupf ned um a Blatt handelt. Im Foi vo gwuazltn Baama wead aa de Wuazl haifig ned ois innara Knupf ogseng.

### Inzidenz

:**Inzidenz** bezeichnet a Beziahung zwischn Knupf und Kantn in am ungrichtetn Graphn. A Knupf hoasst in am ungrichtetn Graphn **inzident** mit oana Kantn, wenn ea vo dera Kantn beriat wead, des hoasst, wenn de eam enthoit. 
:Ba gerichtetn Graphn untascheidet ma zwischn **positiv inzidentn** Kantn und **negativ inzidentn** Kantn. A gerichtete Kantn is positiv inzident zu iam Startknupf und negativ inzident zu iam Endknupf.

:*Schau aaa:* Adjazenz, Inzidenzmatrix, Nochborschoft und Grad in Graphn.

### Inzidenzmatrix

:A **Inzidenzmatrix** zu am Graph mit n Knupf und m Kantn is a n \times m-Matrix, ba dea wo de Zein mit de Knupf und de Spoitn mit dena Kantn identifiziat wean. Dazua nummeriat ma de Knupf vo 1 bis n und de Kantn vo 1 bis m duach und trogt in de Matrix de Beziahunga vo de Knupf zu de Kantn ein.

:Jede Spoitn vo da Inzidenzmatrix enthoit genau zwoai vo Nui vaschiedene Einträg. In ungrichtetn Graphn zwoamoi de 1 und in schleifnfrein grichtetn Graphn oamoi de 1 (Endknupf) und oamoi de −1 (Startknupf).

:*Schau aaa:* Repräsentation vo Graphn im Computer.

### Inzidenzrelation

:Zua Definition sea oigmoana, nämle ungrichteta Graphn mit Schlingen (Kantn vo am Knupf zu si sejm) und paralleln Vabinda (Meafochvabinda) reicht de vaoafochende Graphndefinition G = (V, E) mit e \in E := \{u, v\} mit u, v \in V ned aus, denn do miasstn z. B. in E Duplikate erlaubt sein. Ma fiaht dahea a **Inzidenzrelation** ein und benennt de Elemente aus E mit am eindeitigen Nama e \in E, wo ned vo de Knupf vo de Kantn obhängt. Middls soichana eindeitiga Elemente kenna etzad aa Meafochkantn und Schlingen definiat wean. De Inzidenzrelation wead dann definiat ois I \subseteq V \times E, d. h. zu jedn Knupf wead fia jede Kantn, wo eam beriat, a Element \{v, e\} mit v \in V und e \in E in I afgenumma. Schlingen wean somit iwa jeweis a Element vo da Inzidenzrelation, zwoa parallele Vabinda iwa via Elemente vo da Inzidenzrelation eindeitig repräsentiat.

### Inzidenzvektor
:Zu oana beliabig vorgeban Nummeriarung vo de Kantn A=\{a_1,a_2,...a_m\} is a Element x=(x_i) \in \mathbb{R}^m a *Inzidenzvektor zua (gwichtetn) Kantnmenge <math>M</math>*, fois x_i=
\begin{cases} 
 0& \mbox{, falls } a_i \notin M \land {a_i}^{-1} \notin M \\
 1& \mbox{, falls } a_i \in M\\
 -1& \mbox{, falls } {a_i}^{-1} \in M\\
\end{cases} hom de Kantn aussadem a nednegativs Gwicht, wean de Kantneinträg im Vektor mit dem Gwicht multipliziat. De Menge vo oin so beschriebanan Kroas buidn oan Untavektorram vo \mathbb{R}^m, an Zyklenram. De Menge vo de Fundamentalkroas san a Basis. Da Ram eagibt in direkta Summe mitm Kozyklenram ganz \mathbb{R}^m

### Isoliata Knupf

:A **isoliata Knupf** is a Knupf mit Grad 0 (oisdann ohne Nochborn)

### Isomorphie

:Zwoa Graphn G=(V, E) und H=(V', E') hoassn **isomorph**, fois a bijektive Obbuidung \varphi :V\rightarrow V' existiat, sodass fia olle x,y \in V guit: xy \in E genau dann, wann \varphi (x)\varphi (y)\in E'

## J
*[[#top|(zum Seitenofong)]]*

### Jordankuavn

:A Jordankuavn is a stetige und schnittpunktfreie Kuavn mit Ofangs- und Endpunkt, wobei Ofangs- und Endpunkt iwaeinstimma kenna. De Kantn vo am planarn Graphn san Jordankuavn zwischn san Endpunkt in oana Ebene.

## K
*[[#top|(zum Seitenofong)]]*

### k-Baam
:A ungrichteta Graph hoasst k-Baam, wen a wia foigt rekursiv eazeigbor is:
** Da voiständige Graph K_k is a k-Baam. 
** Gibt ma zua an k-Baam G an neien Knupf v dazua, indem ma v mid oin Knupf vo oana Clique vo da Gräss k aus G vabindt, so is da neie Graph emfois a k-Baam.
:A **partiella <math>k</math>-Baam** entstäht duach de Entfernung vo Vabinda aus am k-Baam: Is G = (V, E) a k-Baam, so it H = (V, F) mit F \subseteq E a partiella k-Baam.
:Gelegentli wean aa Baam mitm maximalen Grad k ois k-Baam bezoachnet. Korrekta is in dem Foi de Bezoachnung *<math>k</math>-nära* Baam.

### Kaktusgraph

:A Graph G hoasst **Kaktusgraph**, wen olle seine Kroas poorweis vabindadisjunkt san (si oiso häxtns gmoasame Knupf tein).
:A Graph G is nacha a Kaktusgrap, wen de Ozoi vo seine Kroas seim Index \mu (G) entsprecha duad.

### Kindl

:**Kindl** [dt. *Kind*] is da Nama fia an direktn Nochfoiga in am Baam.

### Knupf

:A **Knupf** (dt. *Knoten* oda *Ecke*) is a Element vom Knupfhaffa (*Knotenmenge*) vo am Graphn. Dea Haffa vo de Knupf vo am Graphn G hoasst ma moast mit V(G) (fia engl. *vertex*). Graphen bestenga nebn an Knupfhaffa no aus an speziejn Haffa vo Vabinda, dea wo bschreibt, wia de Knupf iwa vabinda zammhänga.

### Knupfdisjunkta Weg

:Zwoa Weg hoasst ma **knupfdisjunkt** oda **kreizungsfrei** (dt. *knupfdisjunkt*), wens koane gmoasaman Knupf hom. Knupfdisjunkte Weg san imma aa vabindadisjunkt (dt. *kantendisjunkt*). (Vabindadisjunkte Weg) san owa ned unbedingt knupfdisjunkt!)

### Knupffärbung

:Eine p-**Knupffärbung** (dt. *Knotenfärbung*) is a Obbuidl vo am Knupfhaffa af den Haffa (dt. *Menge*) \{1, \ldots, p\} (oiso wead an jedn Knupf oane vo p Zoin oda „Forbn“ zuagwiesn).

### Knupffeabungszoi

:*Schaug:* Kromatische Zoi.

### Knupffejd

:A Knupffejd (dt. *Knotenfeld*) is a Dorstejungsart fia grichtade Graphn mid foigandn Afbau:

:|V|, |E|, \text{ag}(V_1), \text{Zui}_1, \ldots, \text{Zui}_{\text{ag}(V_1)}, \ldots, \text{ag}(V_), \text{Zui}_1, \ldots, \text{Zui}_{\text{ag}(V_)}

:wobei |V| de Ozoi vo de Knupf, |E| de Ozoi vo de Vabinda und ag(V) Ausgangsgrad vom Knupf san.

### Knupfpanzyklische Graphn

:A Graph G hoasst **knupfnpanzyklisch**, wen jeda Knupf af am Kroas vo da Läng p liegt, fia olle p \in \{1,2,\ldots,|V(G)|\}.
:Vabindapanzyklische Graphn san knupfpanzyklisch, knupfpanzyklische Graphn san panzyklisch.

### Knupfibadeckung

:Ois **Knupfibadeckung** in am ungrichtadn Graphn hoasst ma an Teihaffa U vo seine Knupf, fia de wo guit, dass jeda Vabinda wenigstns oan Knupf aus U enthoid.
:U is a Knupfibadeckung in G gdw. \forall e \in E, \exists v \in U: v \in e.

### Knupfibadeckungszoi

:Oiss **Knupfibadeckungszoi** vo am ungrichtadn Graphn is de kloanste Zoi k gmoant, fia de wo a Knupfibadeckung vo da Gress k existiad.

### Knupfzammahangszoi

:De **Knupfzusammenhangszoi** (oft kuaz **Zammahangszoi** gnennd) \kappa (G) vo am Graphn G is de kloanste Ozoi vo Knupf, dena eana Entfeanung an Zammahang zastead.

### Komplement

:*Schaug:* Komplementeara Graph.

### Komplementeara Graph

:Da Komplementeare Graph \overline{G} vo am Graphn G hod de gleiche Knupfmenge wia G und in \overline{G} san zwoa Knupf x und y genau dann Adjazent, wenn se s in G ned san (\overline{G} hod oisdann genau de Kantn, wo G ned hod).

:Als **Sejmkomplementea** bezeichnet ma Graphn, wo isomorph zu iam Komplementean Graphn san.

### Komplementgraph

:*Schaug:* Komplementeara Graph.

### Kozyklenram
Is da Vektorram vo olle duach Schnitte erzeigtn Inzidenzvektorn. Ea is Untaram vom \mathbb{R}^m und gibt in direkta Summe mitm Zyklenram an ganzn Ram. A Basis is imma duach de Fundamentalschnitt gem.

### Kroas

:A **Kroas** C=(v_1, v_2, \ldots, v_p, v_1) is a Foign vo Knupf, wo bis auf an easchtn und letztn Knupf poarweis vaschiedn san, wobei sowoi v_i und v_{i+1} fia olle i=1, \ldots, p-1 ois aa v_p und v_1 adjazent sein miassn.

:Enthoit a Kroas olle Knupf vom Graphn, so nennt man Hamiltonkroas.

:A Graph wo nua aus am Kroas (vo da Leng n) bsteht bezeichnet ma mit C_n.

### Kreizungsfreie Weg

:Weg hoassn **kreizungsfrei**, wann se koan gmoasaman innan Knupf hom.

### Kubischa Graph

:A Graph is **kubisch**, foisa 3-regulea is.

## L
*[[#top|(zum Seitenofong)]]*

### Leng vo am Kroas

:De **Leng vo am Kroas** is de Ozoi vo seine Kantn.

### Leng vo am Pfad

:*Schaug:* Leng vo am Weg.

### Leng vo am Weg

:De **Leng vo am Weg** is de Ozoi vo seine Kantn.

### Leng vo am Zyklus

:*Schaug:* Leng vo am Kroas.

### Linegraph

:*Schaug:* Kantngraph.

## M
*[[#top|(zum Seitenofong)]]*

### Matching

:*Schaug:* Poarung.

### Matchingzoi

:*Schaug:* Poarungszoi.

### Maximale Clique

:A **Maximale Clique** C vo am Graphn G is a Teigraph vo G, wo a voistendiga Graph is, und wo in koam gressan Teigraphn vo G enthoidn is, wo aa a voistendiga Graph is.
:Gibt es in G aussadem koan voistendign Teigraphn, wo mea Knupf ois C enthoit, so nennt ma C **gresste Cliqun**.

### Maximale Poarung

:A Poarung M is ae maximale Poarung, wann koa Poarung N mit |N|>|M| existiat.
:**Satz von Berge (1957):** A Poarung M is genau dann a maximale Poarung, wann koa ''M''-alterniarenda Weg existiat.

### Maximals Matching

:*Schaug:* Maximale Poarung.

### Maximalgrad

:Da **Maximalgrad** \Delta (G) vo am Graphn G is de gresste Zoi m, fia de in G a Knotn vom Grad m existiad.
:Entspricht da Maximalgrad am Minimalgrad, so redd ma vo am regulearn Graphn.

### Meafochkantn

:Zu ana **Meafochkantn** oda **Multikantn** fosst ma a Menge vo Kantn zamma, wo zwischn densejm Knotn valaffa und in grichtetn Graphn zuasätzle identische Orientierung besitzn.

:*Schau aaa:* Typn vo Graphn in da Graphntheorie.

### Meafochschleifn

:A **Meafochschleifn** is a grichtete Meafochkantn, wo zgleich Schleifn is.

### Metrischa Graph

:A **Metrischa Graph** is a kantnbewerteta Graph, wo de Dreiecksungleichung erfuit, d. h. san a,b,c \in V(G), so guit stets d(a,c) \le d(a,b)+d(b,c), wobei d(a,b) de Bewertung vo da Kantn \{a,b\} is.

:Intuitiv formuliat: da Weg vo a iwa b noch c deaf ned kiaza sein, ois da direkte Weg vo a noch c.
:Distanzgraphn san stets Metrisch.

### Metrisches Traveling-Salesman-Problem

:Des **Metrische Travelling Salesman Problem** (vagleich: Travelling Salesman Problem) is de Frog noch am kiazestn Hamiltonkroas in am voistendign, kantnbewertetn, metrischn Graphn.
:Des Problem is NP-Voistendig

:*Schau aaa:* Problem vom Handlungsroasendn.

### Minimalgrad

:Da **Minimalgrad** \delta (G) vo am Graphn G is de kloanste Zoi m, fia de in G an Knotn vom Grad m existiat.
:Entspricht dar Minimalgrad am Maximalgrad, so spricht ma vo am regulearn Graphn.

### Minor

:A Graph H is **Minor** vo am Graphn G, fois H aus G duach beliabig vui Kantnkontraktiona entsteet.

### Multigraph
:Mit **Multigraph** bezeichnet ma an Graphn mit Meafochkantn

### Multikantn

:*Schaug:* Meafochkantn.

## N
*[[#top|(zum Seitenofong)]]*

### Nochboar

:A Knotn x is **Nochboar** vo am Knotn y genau daun, wann \{x,y\}\in E(G) oiso wanns duach a Kantn vabundn san.

:Bei grichtetn Graphn untascheidet ma **positive -** und **negative Nochboarn**. Genau daun, wann (x,y)\in B(G) a grichtete Kantn vo x nach y fiat, nennt ma y positivn Nochboarn vo x und x negativn Nochboarn vo y.

### Nochboarschoft

:De **Nochboarschoft** N(v) vo am Knotn v is de Menge vo seine Nochboarn.

:Bei grichtetn Graphn untascheidet ma de **positive Nachboarschaft** N^+(v) (de Menge vo de Knotn, zu dena a grichtete Kantn vo v aus fiat) und de **negative Nochboarschoft** N^-(v) (de Menge vo de Knotn, vo dena aus a gerichtete Kantn zu v fiat)

:De **Obgschlossene Nochboarschaft** is N[v] = N(v)\cup \{v\} oiso nix ondas ois de Nochboarschoft vo v, zu dea v sejm hinzuagfigt woan is. (analog san N^+[v]=N^+(v)\cup \{v\} und N^-[v]=N^-(v)\cup \{v\} definiat)

### Nochboarschoftslistn

:*Schaug:* Adjazenzlistn.

### Nochboarschoftsmatrix

:*Schaug:* Adjazenzmatrix.

### Nochfoiga

:A Knotn v hoasst **Nochfoiga** vo am Knotn u in am grichtetn Graphn fois s an Pfad gibt, wo vo u noch v geht.

### Nochfoigamenge

:De Menge vo oin Nochfoigan vo am Knotn v. Oisdann olle in am Graphn vo v duach an Pfad erreichboarn Knotn.
: Formei: \forall w: \exist (v,\ldots, w) mit v,w \in V ('schaug aa:* [[Transitive Hülle|Transitive Huin]])

=== Netzweak ===

:A *'Netzweak** is a [[#Gerichteta Graph|gerichteta]], [[#Kantnbeweateta Graph|kantnbeweateta]] Graph mit zwoa ausgezeichneten [[#Knotn|Knotn]], vo da [[#Quejn|Quejn]] und da [[#Senkn|Senkn]].
:De Kantn deafn nua positiv beweatet sein und de Kantnbeweatung wead in dem Zammahang in da Regel ois **Kapazität** vo dar grichtetn Kantn bezeichnet.
:In Netzweakn wean haptsächle sognennde [[#Fluss|Flisse]] betrocht. Moast is ma dobei am maximal meglichn s-t-Fluss interessiat, den ma beispuisweis mit am [[Algorithmus von Edmonds und Karp|Edmonds-Karp-Algorithmus]] berechnen ko.

== O ==
''[[#top|(zum Seitenofong)]]''

=== Oafocha Graph ===

:Ois **oafocha Graph** oda aa ''schlichta Graph** wead a Graph ohne bsondare Strukturelemente wia Meafochkantn, orientiate Kantn, Schleifn, Knotn- oda Kantngwichte bzw. Feabungen oda Markiarungen bezeichnet.

### Oafocha Kroas

:A oafocha Kroas in am schlichtn, ungrichteten Graphn G = (V, E) is a Kroas, wo jedn Knotn v \in V genau a Moi enthoid.

### Oafocha Pfad

:A oafocha Pfad in am schlichtn, ungrichtetn Graphn G = (V, E) is a Pfad, wo jedn Knotn v \in V genau a Moi enthoid.

### Obagraph

:A Graph G is a **Obagraph** vo am Graphn H, wann H a Teigraph vo G is.

### Obstand

:*Schaug:* Distanz.

### Ongl

:Untam **Ongl** vo am Knotn v in am Binärbaam vasted ma an Sohn vom Grossvodda vo v, wo ned da Vodda vo v is.

### Ordnung vo am Baam

:Ois **Ordnung** vo am Out-Trees wead de gresste Ozoi vo Kinda vo oam vo seine Knotn bezeichnet.

## P
*[[#top|(zum Seitenofong)]]*

### Poarung
:A **Poarung** (aa **Matching**, **Zuaordnung** oda **unobhängige Kantnmenge**) in am ungrichteten Graphn G = (V, E) is a Menge E' \subseteq E mit da Eigenschoft, dass koane zwoa Kantn aus E' in G duach an gmoasamen Knotn vabundn san:

:E' is unobhängi in G gdw. \forall e,e' \in E',\  mit\  e \not= e': e \cap e' = \varnothing.

:*Schau aaa:* perfekte Poarung, maximale Poarung.

### Poarungszoi

:De **Poarungszoi** is de vo oana maximein Poarung.

### Panzyklische Graphn
:A Graph hoasst **panzyklisch** wann a fia olle p \in \{1,2,\ldots,|V(G)|\} oan Kroas vo da Läng p besitzt.
:Insbesondas san panzyklische Graphn damit hamiltonsch.

:*Schau aaa:* Knotnpanzyklische Graphn, Kantnpanzyklische Graphn.

### Parallele Kantn

:Zwoa Kantn hoassn **parallel**, fois se zwischn ansejm Knotn valaffa, d. h. zua ansejm Knotn inzident san.

### Partieller k-Baum

:*Schaug:* k-Baam.

### Partition

:G=(V, E) is a Graph is A Zalegung (Partition) vo da Knotnmenge V in p disjunkte Teimengen V_1...V_p hoasst **<math>p</math>-Partition**, fois koane adjazentn Eckn in am gmoasamen V_i liegn. (Oschauli hoasst des: olle Kantn valaffen zwischn dena Teimengen, koane innahoib vo oana vo de Teimengen.)

**Besitzt a Graph G a p-Partition, so soggdma aa „G is **<math>p</math>-partit**“ oda „G is a **<math>p</math>-partiter** Graph“.
**De chromatische Zoi vo G is des kloanste p, sodass G a p-Partition besitzt (feab olle Elemente vo oana Partitionsmenge mit da gleichn Foab).
**In da Praxis orbat ma haifi mit Poarungen in bipartite (2-partitn) Graphn.

### Perfekte Eliminationsordnung

: Ois **perfekte Eliminationsordnung** bezeichnet ma a Knotnreihenfoig (v_1, v_2, \ldots, v_n), V = \{v_1, v_2, \ldots, v_n\} vom Graphn G = (V, E), so dass fia jedn Graphn mit da (duach Eliminiarung vo de Knotn v_1 bis v_{i-1}) eingschränktn Knotnmenge G_i = (\{v_i, \ldots, v_n\}, E_i) guit: v_i is simplizial in G_i. Jeda (in Bezug af de gewejde Ordnung) „kloanste“ Knotn in G_i buidt oisdann mit seim Nochboarn a Cliquen. Des guit beispuisweis fia olle Bladdln vo am Baam, so dass a sukzessivs Eliminian vo Bladdln vo am Baam a perfekte Eliminationsordnung fia an Baam liefat.

### Perfekte Poarung

:A **perfekte Poarung** (aa **voiständige Zuaordnung**) is a Poarung M, wo jeda Knotn mit genau ana Kantn aus M inzidiat.

### Perfektes Matching

:*Schaug* Perfekte Poarung.

### Pfad

:A Pfad P=(v_1, v_2, \ldots, v_p) is a Foign vo Knotn, mit poarweise vaschiedanen Knotn, wobei imma v_i und v_{i+1} adjazent sein müssen für alle i=1,\ldots,p-1.

:Enthoit P olle Knotn vo G, so nennt man P an Hamiltonpfad.

:Fordat ma ned, dass de Knotn vo P poarweis vaschieden san, so redd ma vo am Weg.

### Planara Graph

:A **planara Graph** is a Graph, wo si in da Ebene doarstejn losst, ohne dass si seine Vabinda schneidn.
****Sotz vo Kuratowski:** A Graph is genau dann planar, wenna koan Teigraphn enthoit, wo an voiständign Graphn K_5 odar K_{3,3} ois Minor hod.

:*Schaug:* Planarer Graph.

### Pseudo-achromatische Zoi
:De **pseudo-achromatische Zoi** \psi_s (G) vo am Graphn G is de gresste Zoi k, fia de wo G a voiständige Knotenfeabung hod.
:Im Gegnsotz zua achromatischn Zoi is do ned de Guitigkeit da Feabung valangt.

:*Schau aaa:* chromatische Zoi, achromatische Zoi.

## Q
*[[#top|(zum Seitenofong)]]*

### Quejn

:A **Quejn** in am grichtetn Graphn is a Knotn, wo koan Vorgänga hod.
:Im Zammahang mit Flissn vasteht ma unta oana Quejn an Knoten, wo meara Fluss aussakimmt oid einegeht.

:*Schau aaa:* Senkn.

## R
*[[#top|(zum Seitenofong)]]*

### Rand

:Da **Rand** entspricht da Menge vo oin Knotn maximala Exzentrizität vo am Graphn.

### Reguleara Graph

:A Graph hoasst **regulea**, fois olle seine Knotn an gleichn Grad (ungrichtetn Graphn) bzw. an gleichn Eingangs- und Ausgangsgrad (grichteta Graph) hom. Is da Grad vo oin Knotn vo am regulean Graphn k, so hoasst ma den **<math>k</math>-regulea**. A Wurzlbaam hoasst k-regulea, wenn olle Knotn mit Ausnohm vo de Bladdln an Ausgangsgrad k hom.

:*Schau aaa:* Nochboarschoft und Grad in Graphn.

### Radius

:Da **Radius** R(G) vo am Graphn G is des Minimum vo de Exzentrizitätn vo de Knotn vo G.
:Fia olle Graphn G guit R(G)\le D(G)\le 2 \cdot R(G), wo D(G) da Duachmessa vo G is.
:De Knotn, vo dena de Exzentrizität am Radius entsprecha duat, buidn des Zentrum vo G.

### Ruckweatskantn

: *Schaug:* Vorweatskantn.

## S
*[[#top|(zum Seitenofong)]]*

### Sotz vom Hall

:*Schaug:* Hozadssotz.

### Schleifn

:Ois **Schleifn** oda **Schlingen** wead in am Graphn a Kantn bezeichnet, wo an Knotn mit si sejm vabindd, des hoasst a Kantn vo da Foam (v, v).

:*SSchau aaa:* Meafochschleifn.

### Schleifnfreia Graph

:*Schaug:* Schleifenlosa Graph.

### Schleifnlosa Graph

:Ois *schleifnlosn*' od *schleifnfrein Graphn*' bezeichnet ma an grichtetn Graphn, wo koa Schleifn enthoid.

### Schlinge

:*Schaug:* Schleifn.

### Schnitt

:A Zalegung (oda Partition) S(X,Y)\! vo da Knotnmenge V vo am Graphn in zwoa nichtlaare Teimengen X\subset V und Y\subset V mit X\cup Y=V\! und X\cap Y=\varnothing hoasst **Schnitt**.
:Da Begriff spuit bsondas ba Netzwerkn mit auszeichnetn Knotn q (vo da Quejn) und s (vo da Senkn) a Roin. Do nennt ma a Teimengen S vo Knotn, wo q owa ned s enthoit, an Schnitt. De Vaeinigungsmengen vo de Kantn, vo vo S noch V \ S fian sowia vo de Kantn, wo vo V \ S noch S fian, nennt ma *an duach S definiatn Schnitt*. Ma redd dann aa, wenn im Kontext jeweis kloar is, ob de Knotn- oda de Kantnmenge gmosnt is, vom Schnitt S und moant de duach S definiate Kantnmenge.

### Schnittknotn

:A **Schnittknotn** in am Graphn G is a Knotn k wo guit, dass G-k mindastns a Zammahangskomponentn meara hod, ois G. D.&nbsp;h. dass de Zammahangskomponentn, in dea wo k liegt, duach Entferna vo k zafoit. Ondas ausdruckt: es existian Knotn x und y fia de *jeda* Weg vo x noch y iwa k fiat.

### Schwoche Zammahangskomponentn

:A *schwoche Zusammenhangskomponentn*' vo am grichtetn Graphn is a maximale Teimenge vo seine Knotn, wo zwischn je zwoa beliabign Knotn vo dera Menge a ungrichteta Weg existiat (dazua muass ma a jede grichtete duach a ungrichtete Kantn easetzn).

### Sehne

:In am Graphn G bezeichnet **Sehne** a Kantn vo G, wo zwoa Knotn vo oam Kroas in G vabindt, sejm owa ned a Tei vo am Kroas is.

### Semieulerscha Graph

:A Graph hoasst *semieulersch*', wann in eam a Eulerweg existiat. A Eulertour is zwor ebmfois a Eulerweg, owa in da Regel moant ma mit „semieulersch“ dass koa Eulertour existiat, wei ma in so am Foi vo am eulerschn Graphn redn dad.

### Semihamiltonscha Graph

:A Graph hoasst *semihamiltonsch*', wann in em a Hamiltonpfad existiat. A Hamiltonkroas induziat zwor Hamiltonpfade, owa in da Regl meoant ma mit „semihamiltonsch“ dass koa Hamiltonkroas existiat, wei ma in dem Foi vo am hamiltonschn Graphn redn dadat.

### Senkn

:A **Senkn** is a Knotn in am grichtetn Graphn, wo koan Nachfoiga hod.
:Im Zammahang mit Flissn vasteht ma unta ana Senkn an Knotn, wo mehra Fluss einigeht ois aussafliasst.

:*Schau aaa:* Quejn.

### Separator

:G = (V, E) is a endlicha, ungrichteta, schlichta Graph. A Knotnmenge S \subseteq V hoasst dann Separator fia zwoa ned bednochboarte Knotn a, b \in V gdw. a und b in G(V \setminus S) in vaschiednan Zammahangskomponentn liegn.

### Simpliziala Knotn

: A Knotn v \in V vom Graphn G = (V, E) hoasst ma *simplizial*', wann a gmoasam mit oi seine Nachboarn a Cliquen, d. h. an voiständign Teigraphen in G buidd.

### Spannbaam
:A **Spannbaam** (a *spannenda Baam*' gnennt) vo am Graphn is a Teigraph, wo a Baam is und olle Knotn vom Graphn enthoit.

:*Schau aaa:* Spannbaam.

### Spanna
:A **k-Spanna** vo am Graphn G is a Teigraph, wo olle Knotn umfosst (also spannt) , wo de Distanz vo jedn Knotnpoar hechstns am k-fochn vo seina Distanz in G entspricht.

### Spannwoid
:*Schaug* Grist.

### Stabile Menge

:Ae *stabile*' oda **unobhängige** Menge (Independent Set) is in am ungrichtetn Graphn a Menge vo Knotn, zwischn dena koa Kantn verlafft.

:*Schau aaa:* Kontniwadeckunga, Cliquen und stabile Mengen.

### Stabilitätszoi

:Ois **Stabilitäts-** oda **Unobhängigkeitszoi** bezeichnet ma de Ozoi vo de Knotn in oana gresstn stabiln Menge.

:*Schau aaa:* Kontniwadeckunga, Cliquen und stabile Mengen.

### Stoark zammahängenda Graph

:A grichteta Graph hoasst stoark zammahängend, wann a nua oa stoark Zammahangskomponentn besitzt.

### Stoarke Zammahangskomponentn

:A *stoarke Zammahangskomponentn*' vo am grichtetn Graphn is a maximale Teimenge vo seine Knotn, wo zwischn je zwoa beliabign Knotn vo dera Menge in boade Richtunga mindestns oa grichteta Weg existiat.

### Startknotn vo oana Kantn

:Is k=(x,y) a grichtete Kantn, so bezeichnet mn x ois ian **Startknotn** und y ois ian Endknotn.
:Bei ungerichtetn Kantn k=\{x,y\} ko ma x und y sowoi ois Startknotn ois aa ois Endknotn bezeichna. Do redd ma in da Regl owa oafoch vo de zwoa „zu k inzidentn Knotn“.

### Stern

:A Graph vom Grad k is a Stern, wann a Knotn (de Mittn vom Stern) Grad k (Kantn zu oin ondan Knotn) hod, und olle ondan Knotn Grad 1 hom (nua mit am Knotn in da Mittn vabundn san).

### Subgraph

:*Schaug:* Teigraph.

### Symmetrischa Graph

:A **[[symmetrischa Graph]]** is a grichteta Graph, wo mit jeda Kantn (u,v) aa de Kantn (v,u) enthoit.

:*Schau aaa:* Typn vo Graphn in da Graphntheorie.

## T
*[[#top|(zum Seitenofong)]]*

### Taillenweitn

:De **Taillenweitn** \tau (G) vo am Graphn G is de Läng vo am kiazestn Kroas in G. Is G a Woid (hod oisdann koane Kroas) so setzt ma \tau (G) = \infty.

### Teigraph

:A *Teigraph* vo am Graphn G is a Graph, wo duach Wegganehma vo beliabign Knotn und Kantn aus G entsteht (Omeakung: beim Entfeana vo am Knotn k foin aa olle mit k inzidentn Kantn wegga).

:*Schau aaa:* Obagraph, Induziata Teigraph.

### Topologische Ordnung

: De Knotnreihenfoige vo am grichtetn, azyklischn Graphn hoasst **topologische Ordnung** oda **topologische Sortiarung**, wann fia olle Kantn (u,v) vom Graphen guit: u liegt in dera Reihnfoige vor v.

### Topologische Sortiarung

: *Schaug*: Topologische Ordnung bzw. Topologische Sortiarung.

### Travelling Salesman Problem

:Des **Travelling Salesman Problem** (Problem vom Handlungsreisendn) is de Frog noch am kiazestn Hamiltonkroas in am voiständign, kantnbewertetn Graphn, oisdann a Kroas, wo jedn Knotn genau amoi passiat und a minimale Summe vo de Kantnbewertunga vo de passiatn Kantn hod.

:*Schau aaa:* Problem vom Handlungsreisendn.

### Trianguliarta Graph

:A endlicha, schlichta und ungrichteta Graph hoasst **trianguliat** oda aa **chordal**, wann a koane induziatn Kroas C_n mit n \geq 4 enthoit. Mit ondan Woartn: Jeda induziate Kroas is a Dreieck (lat. *triangulum*). Ma nennt dabei oan Kreis induziat, wann zwischn dena Knotn, wo an Kreis buidn, *koane weidan Kantn* (sognennfe Sehnen, engl. *chord*) im Ursprungsgraphn existian.

:*Schau aaa:* Trianguliata Graph.

### Triviale Partition

:De **Triviale Partition** vo am Graphn is de Partition, wo jeda Knotn in oana oaganen Partitionsmenge liegt.

### Triviala Kroas

:De Foign (v) vo Knotn, wo aus nua oam Knotn besteht, eafuit de Definition vo am #Kroas

### Triviala Zyklus

:De Foign (v) vo Knotn, wo aus nua oam Knotn besteht,eafuit de Definition vo am Zyklus

### Turniagraph

:A **Turniagraph** is a Graph, wo zwischn je zwoa Knotn genau a Kantn existiat.

:*Schau aaa:* Turniagraph

## U
*[[#top|(zum Seitenofong)]]*

### Umfang

:De Läng vom längstn Weg in am Graphn is sei **Umfang**.

### Unobhängige Knotnmenge
:A **unobhängige Knotnmenge** in am ungrichteten Graphn G = (V, E) is a Menge U \subseteq V mit da Oagnschoft, dass koane zwoa Knotn aus U in G duach a Kantn vabunden san: 
:U is unobhängig in G gdw. \forall u,v \in U: {u, v} \notin E.

### Unobhängige Kantnmenge
:*Schaug* Poarung.

### Unobhängige Menge

:*Schaug:* Stabile Menge.

### Unobhängigkeitszoi

:*Schaug:* Stabilitätszoi.

### Unendlicha Graph

:A **unendlicha Graph** is a Graph, vo dem sei Knotnzoi unendle os.

:*Schau aaa:* Unendlicha Graph

### Ungrichtete Kantn

:A **ungrichtete Kantn** vabindd zwoa Knotn vo oam Graphn ohne Beochtung vo oana Reihnfoige. A ungrichtete Kantn wead dahea ois zwoaelementige Menge vo Knotn notiat.

:*Schau aaa:* Grichtete Kantn, Typn vo Graphn in da Graphntheorie.

### Ungrichteta Graph

:A **ungrichteta Graph** is an Graph, wo koane grichtetn Kantn enthoit.

:*Schau aaa:* Typn vo Graphn in da Graphntheorie.

### Uniforma Hypergraph

:A **uniforma Hypergraph** is a Hypergraph, in dem olle Hyperkantn glei vui Knotn miteinanda vabindn.

### Universala Knotn

:A **universala Knotn** is a Knotn, wo zu oin ondan Knotn im Graphen adjazent is.

### Untabaam

:A *Untabaam* is a speziella Teigraph vo am Baam, wo sejm ois kompletta Baam ogseng wean ko.

### Untagraph

:*Schaug:* Teigraph.

### Unzammahängenda Graph

:A **Unzammahängenda** is a Graph, wo mindestns zwoa Zammahangskomponentn hod.

## V
*[[#top|(zum Seitenofong)]]*

### Vabinda

:A **Vabinda** is a Element vom Vabindahaffa vo am Graphn. Da Vabindahaffa vo am Graphn G wead moast mit E(G) (fia engl. *edge*) bezoachnet. Se bschreibt, wia de Knupf vom Knupfhaffa vom Graphn miteinanda vabundn san. Je nach Typ vom Graphn untascheidn si de meglichen Forma vo Vabinda.

### Vabindabeweatada Graph

:A **vabindabeweatada Graph** is a Graph G mit ama Vabindabeweatung g, de wo formal a Obuidl vom Vabindahaffa af de reelln Zoin is. De Vabindabeweatungsfunktion g bezoachnet ma oft aa ois **Kostnfunktion** oda **Vabindagewichtsfunktion**.
:Vabindabeweatunga spuin haife a Roin in Optimiarungsafgom, wia beispuisweis beim Travelling Salesman Problem, wobei de Bewertunga z.&nbsp;B. fia Fohrtzeidn af vaschiednann Stroßn (Gschwindigkeitsbegrenzunga, Staus), Fohrtkosten (Maut, Benzinvabrauch) oda Strecknläng stäht.

### Vabindafärbung
:Is G=(V, E) a ungrichteda Graph ohne Meafochvabinda und f a vo E in de Haffa vo de natialichn Zoin \mathbb{N}_0, so nennt ma f a **Vabindafärbung** vo G.

### Vabindadisjunkte Wege

:Zwoa Wege hoassn **vabindadisjunkt**, wens koa gmoasaman Vabinda hom. Im Gegnsotz zu disjunktn Wegn deafa vabindadisjunkte Wege mearane Knupf gmoasam enthoidn.

### Vabindafärbungszoi

:*Schaug:* Chromatischa Index.

### Vabindafejd

:A Vabindafejd is a Doastejungsoart fia grichtade Graphn nocham foigendn Schema:

:|V|, |E|, E_1,\ldots, E_

:wobei |V| de Ozoi vo de Knupf, |E| de Ozoi vo de Vabinda und  E_1, \ldots, E_ de Vabinda san mid  E_i = (v, w) \in E .

### Vabindagraph

:Da **Vabindagraph** (engl. line graph) L(G) vo am Graphn G entstähd so aus G:
**Fia jedn Vabinda k aus G setz an Knupf k' in L(G).
**Bau an Vabinda \{k', l'\} in L(G) genau nacha ei, wen de Vabinda k und l in G an gmoasama Endknupf hom.

### Vabindakontraktion

:Is k a Vabinda, dea wo de Knupf x und y vabindet, nacha is de **Kontraktion** vo k a „Vaschmejzung“ vo x und y, d.&nbsp;h. x, y und k wean duach an neien Knupf z dasezt, dea wo mid oin Nochbarn vo x und y vabundn wead.
:Hom x und y an gmoasama Nochbarn w, so valaffa im resultiarendn Graphn parallele Vabinda zwischn z und w oda oigmoana: wen zwischn x und w n parallele Vabinda und zwischn y und w m parallele Vabinda valaffa, so valaffa noch da Kontraktion vo k zwischen z und w genau m+n parallele Vabinda.

### Vabindapanzyklische Graphn

:A Graph hoasst **vabindapanzyklisch** fois jeda Vabinda af am Kroas vo da Läng p liegt fia olle p \in \{1,2,\ldots,|V(G)|\}. Vabindanzyklische Graphn san aa knupfnpanzyklisch und so aa panzyklisch.

### Vabindaibadeckung
:A **Vabindaibadeckung** in am ungrichtadn Grapen G = (V, E) is a Haffa E' \subseteq E mid da Oagnschoft, dass a jeda Knupf vo V in am Vabinda aus E' enthoidn is.
:E' is a Vabindaibadeckung in G gdw. \forall v \in V, \exists w \in E': v \in w.

### Vabinda-Untateilung

:A **Untateilung** vo am Vabinda is as Eibaun vo am Knupf.
:Formal: It G=(V, E) a Graph und k=\{x, y\} \in E, so entstäd G' duach Untateilung vo k ois G'=(V \cup \{z \notin V\}, E \setminus \{k\} \cup \{\{z,x\},\{z,y\}\}). De Voraussezung z\notin V is fia de formale Korrektheid noudwendi.

### Vabindazammahangszoi

:De Vabindazammahangszoi (dt. *Kantenzusammenhangszahl*) vo am Graphn hoasst ma de Ozoi vo de Vabinda, de wo ma wegganehma muass, damid da Zammahang vaschwindt.

### Valenz

:*Schaug:* Grad.

### Valenzsequenz

:*Schaug:* Gradfoign.

### Vodda

:**Vodda** is da Nom fian direktn Voagänga in am Baam.

### Vabesserungspfad

:Is G a Graph und M\subseteq E(G) a Poarung in G, dann is a **Vabesserungspfad** (aa **<math>M</math>-alterniarenda Pfad**) a Pfad w, wo obwechselnd Kantn aus M und Kantn aus E(G)\setminus M enthoit, wobei **an boadn Endn** Knotn liagn, de wo mit koana Kantn aus M inzidian (oiso san aa de boadn Endkantn vo w aus E(G)\setminus M).
:A soicha Pfad hoasst Vabesserungspfad, wei ma a Poarung N mit |N| = |M|+1 dahoidn ko, indem ma de Kantn vo w, wo in M liagn aus M entfeant und dafia de andan Kantn vo w zu M dazudoa.

:**Satz vo Berge (1957)**: A Poarung is genau dann maximal, wanns koan Vabesserungspfad gibt.

### Vagleichborkeitsgraph

:A (gerichteta) **Vagleichborkeitsgraph** is a grichteta Graph, vo dem seine Kantn a Ordnungsrelation af seine Knotn entsprechn. Sei beispuisweise O = (V,  a Hoibordnung af da Knotnmenge V vom Graphn G = (V, E), so guit fia jede Kantn (u, v) \in E de Beziahung u . 
:Von am **ungrichtetn Vagleichborkeitsgraphn** redd ma, wann fia jede Kantn (u, v) \in E guit: (u  oda v ).

### Voiständige Knotenfeabung

:A **voiständige Knotenfeabung** is a Knotenfeabung, ba dea wo fia jeds Poar \{i,j\} vo Foarbm a Kantn \{x,y\}\in E(G) existiat, sodass x mit i und y mit j gfeabt is. D.&nbsp;h. dass fia jeds Foarbmpoar benochboarte Knotn existian, wo mit dena Foarbm gfeabt san.
:Obocht: a voiständige Knotnfeabung muass ned notwendi a gitige Knotenfeabung sein.

:*Schau aaa:* chromatische Zoi, achromatische Zoi, pseudo-achromatische Zoi.

### Voiständige Zuaordnung

:*Schaug:* Perfekte Poarung.

### Voiständiga Graph

:A **voiständiga Graph** is a Graph, ba dem jeda Knotn mit jedn ondan Knotn duach genau a Kantn vabundn is. 
**An voiständign Graphn mit n Knotn bezeichnet ma mit K_n
:A **voiständiga <math>p</math>-partita Graph** is a ''p''-partita Graph ba dem jeds Poar vo zwoa Knotn aus *vaschiednan Partitionsmengen* adjazent is
**An voiständign multipartitn Graphn mit p Partitionsmengen, wo n1,...,np Knotn enthoitn, bezeichnet ma mit K_{n1, \ldots, np}

:*Schau aaa:* K_5 und K_{3,3} in Charakterisarung vo planarn Graphn.

### Vorgänga

:A Knotn u hoasst **Vorgänga** vo am Knotn v in am grichtetn Graphn fois s oan Pfad gibt, wo vo u noch v ged.

### Vorgängamenge

:De Menge vo oin Vorgängan vo am Knotn v. Oisdann olle Knotn in am Graphn vo dena v duach an Pfad eareicht wean ko.
: Formei: \forall w : \exist p : p = (w,\ldots, v) mit v,w \in V, p \in P, w \in W wobei V de Knotnmenge, P de Menge vo de Pfade und W de **Vorgängamenge** is, ('schaug aa:* [[Transitive Hülle|Transitive Huin]])

=== Vorweatskantn ===

:Da Begriff *'Vorweatskantn** hod genauso wia de Begriff **Ruckweatskantn**, **Querkantn** und **Baamkantn** a Bedeitung fia de [[Tiefensuche|Diafnsuach]] in Graphn. Ba oana Diafnsuach wean de Kantn vom Graphn, wo vom Diafnsuach-Algorithmus duachlaffa wean, ois Baamkantn bezeichnet. De Kantn, wo ned gnutzt wean und vo am Knotn zu am ondan Knotn im sejm Teibaam fian, dea wo 'spoda bsuacht wead'', hoassn Vorweatskantn. De Kantn, wo ned gnutzt wean und vo am Knotn zu am ondan Knotn im sejm Teibaam fian, dea wo vo da Diafnsuach 'scho voahea bsuacht woan is'', hoassn Ruckweatskantn. De Kantn, wo „quer“ vo am Teibaam zu am ondan Teibaam valaffa, hoassn Querkantn. Innahoib vom Diafnsuachbaam dadad da Pfad zwischn zwoa iwa a Querkantn vabundeanen Knotn znaxt a Af- und dann a Obsteign vom Baam eafoadan. Vorweatskantn, Ruckweatskantn, Querkantn und Baamkantn eagem insgsamt de Kantnmenge vo am Graphn.

== W ==
''[[#top|(zum Seitenofong)]]''

=== Woid ===

:A **Woid** is in da [[Graphentheorie|Graphntheorie]] a [[Ungrichteta Graph|ungrichtets Graph]] ohne [[Wege, Pfade, Zyklen und Kreise in Graphen|Kroas]].
:A Graph is dann a Woid, wann sei [[#Index|Index]] 0 is.

:''Schau aaa:'' [[Wald (Graphentheorie)|Woid (Graphntheorie)]].

=== Weg ===
:A **Weg** <math>W=(v_1, v_2, \ldots, v_p)</math> is a Foign vo Knotn. Dabei miassn imma <math>v_i</math> und <math>v_{i+1}</math> [[Nachbarschaft und Grad in Graphen|adjazent]] sei fia olle <math>i=1,...,p-1</math>.

:San olle Knotn poaweis vaschiedn, so red ma vo am [[#Pfad|Pfad]].

:In da Literatua wead a Pfad moastns ois ''Weg'' und a Weg ois ''Vabindazug'' bezeichnet.

=== Wegiwadeckung ===

:A [[Menge (Mathematik)|Menge]] vo [[#Disjunkte Wege|disjunkte Wege]] in am [[#Grichteta Graph|gerichtetn Graphn]] <math>G</math> mit da Oagnschoft, dass jeda [[#Knotn|Knotn]] vo <math>G</math> af oan vo dena Wegn liegt, hoasst **Wegiwadeckung**.

=== Wuazl ===

:A **Wuazl** is a [[#Knotn|Knotn]], vo wo aus olle andan Knotn vom Graphn erreichbor san.

:''Schau aaa:'' [[#Wuazlbaam|Wuazlbaam]].

=== Wuazlbaam ===

:A **Wuazlbaam** is a [[#Baam|Baam]] <math>B=(V, E)</math> wo a Knotn ois [[#Wuazl|Wuazl]] <math>w\in V</math> auszeichnet is. Baam ohne Wuazl hoasst ma im Gegnsotz zu Wuazlbaam aa ''freie Baam''. In da Literatua wead oft implizit a Wuazlbaam gmoant, wann oigmoa vo am Baaf de Red is. Wuazlbaam hom gegniwa frein Baam oanige bsondare Oagnschoftn:
** Jeda Knotn <math>y</math> af oam oafochn Pfad vo <math>w</math> zu am andan Knotn <math>x</math> hoasst ''Voagänga'' vo <math>x</math>.
** Is <math>y</math> a Voagänga vo <math>x</math> und <math>x \neq y</math>, so hoasst <math>x</math> ''Nochfoiga'' vo <math>y</math>.
** A duach an Vabinda vabundena Voagänga hoasst aa ''Voda'', <math>x</math> hoasst nacha ''Sohn'' vo <math>y</math>.
** De ''Häh'' vo am Wuazlbaam is de maximale Läng vo am Pfad vo da Wuazl bis zu sm Blatt.

== X ==
''[[#top|(zum Seitenofong)]]''

== Y ==
''[[#top|(zum Seitenofong)]]''

== Z ==
''[[#top|(zum Seitenofong)]]''

=== Zentrum ===

:Des **Zentrum** <math>Z(G)</math> vo am Graphn <math>G</math> is de Menge vo Knotn vo <math>G</math>, vo dena de [[#Exzentrizität|Exzentrizität]] am [[#Radius|Radius]] vo <math>G</math> entspricht

:''Schau aaa:'' [[#Duachmessa|Duachmessa]].

=== Zuaordnung ===

:Schaug [[#Poarung|Poarung]].

=== Zammahängenda Graph ===

:A zammahängenda Graph is a Graph, wo nua aus oana [[#Zammahongskomponentn|Zammahongskomponentn]] besteht.

=== Zammahongskomponentn ===

:A **Zammahongskomponentn** vo am [[#Ungrichteta Graph|ungrichteen]] [[#Graphn|Graphn]] is a maximale Teimenge vo seine [[#Knotn|Knotn]], in dea zwischn je zwoa beliabign Knotn vo dera Menge mindastens a [[#Weg|Weg]] existiat.

=== Zammahongszoi ===

:''Schaug:'' [[#Knotnzammahongszoi|Knotnzammahongszoi]].

=== Zyklischa Graph ===

:A **zyklischa Graph** is a [[#Grichteta Graph|grichteta Graph]], wo mindastens oan [[#Zyklus|Zyklus]] enthoit.

=== Zyklomatische Zoi ===

:''Schaug:'' [[#Index|Index]].

=== Zyklus ===

:A **Zyklus*' in oam [[#Graphn|Graphn]] is a [[#Weg|Weg]], wo im sejm [[#Knotn|Knotn]] ofongt und endet.
:A Vabinda liegt genau nacha af am Zyklus, wen sie koa [[#Bruckn|Bruckn]] ist.

:*Schau aaa:* [[Wege, Pfade, Zyklen und Kreise in Graphen|Wege, Pfade, Zyklen und Kroas in Graphn]].

=== Zyklenraum ===
:A *Zyklenraum'' is da Vektorraum vo oin duach (gwichtete) Kroas beschriebanen Inzidenzvektorn. Ea is a Untaverktorraum vo \mathbb{R}^m. In direkta Summe mitm Kozyklenraum eagibt a an ganzn Raum. De Fundamentalkroas san a Basis.