Glossar vo da Graphntheorie

Der Artikl is im Dialekt Obaboarisch gschrim worn.

Des Glossar vo da Graphntheorie enthoit a Stichwortvazeichnis und kuaze Definitionen und Omeakunga zu de wichtigsten Begriffe vo da Graphntheorie

Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

A

Achromatische Zoi

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

Schaug aa: chromatische Zoi, pseudo-achromatische Zoi.

Adjazenz

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

Schaug aa: Inzidenz, Adjazenzmatrix, Nochborschoft und Grad in Graphn.

Adjazenzlistn

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

Schaug aa: Adjazenzmatrix.

Adjazenzmatrix

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

Adjazenzraam

Da Adjazenzraam vo am Graphn is da Vektorraam, wo vo de Spoitn vo da Adjazenzmatrix afgspannt wead.

De Adjazenzraam vo isomorphn Graphn san isomorphe Raam.

Alternierenda Pfad

Schaug: Vabesserungspfad.

Artikulation

A trennende Knotnmenge, wo aus am Knotn besteht, wead Artikulation gnennt.

Augmentierender Pfad

Schaug: Vabesserungspfad.

Ausgangsgrad

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

Schaug aa: Grad, Eingangsgrad, Nochborschaft und Grad in Graphn.

Ausgangsmenge

Ois Ausgangsmenge vo am Knotn wead in am grichtetn Grapnh de Menge vo seim direktn Nochfoiga bezeichnet.

Automorphismus

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

Azyklischa Graph

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

B

(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 Knotn. Dann bezeichnet $\max_{\{i,j\}\in E} |L(i)-L(j)|$ de Bandbroadn in Bezug af $L$ und $\min_L \max_{\{i,j\}\in E} |L(i)-L(j)|$ de Bandbroadn vom Graphn $(V,E)$.

De Eamittlung 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: $G$ 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: Vorweatskantn.

Bipartition

A Bipartition is a 2-Partition.

Bipartiter 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.

Haptartikl: Bipartita Graph, voiständig bipartita Graph.

Schaug aa: Sotz vom König, Wege, Pfade, Zyklen und Kroas in Graphn.

Blatt

A Blatt is a Knotn 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 knotnzammahängend is. Des hoasst, dass wenn a weidane Knotn vo $G$ zu $B$ dazuakematn, dea zua oam vo de ondan Knotn vo $B$ nua oan Weg häd.

Blockgraph

An Blockgraph $block(G)$ zu oam Graphn G eafuit de foigendn Oagnschoftn:

• Fia jedn Schnittknotn in G gibts genau oan Knotn in $block(G)$.
• Fia jedn Block in G gibts genau oan Knotn in $block(G)$.
• Kantn valaffa zwischn Schnittknotn und Blockknotn genau dann, wann da Block an Schnittknotn enthoid.
• Es gibt koane weidan Knotn und Kantn in $block(G)$.

Bogen

Schaug: Grichtete Kantn.

Bruggn

A Kantn $k$ hoasst Bruggn in an Graphn $G$, fois zwoa Knotn $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

(zum Seitnofang)

Chordala Graph

Schaug: Trianguliata Graph.

Chromatische Zoi

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

Schaug aa: 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.

Schaug aa: Feabung.

Clique

A Clique is in am ungrichtetn Graphn a Teimenge vo de Knoten, innahoib vo dena olle Knotn poarweis mit oana Kantn vabundn san.

Schaug aa: Knotniwadeckunga, Cliquen und stabile Mengen.

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.

Schaug aa: Knotniwadeckunga, Cliquen und stabile Mengen.

Cliquenzoi

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

Schaug aa: Cliquenproblem.

D

(zum Seitenofong)

Diafn

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

Schaug aa: Heh.

Dichtn

De Dichtn $dn(G)$ vo am oafochn Graphn $G=(V, E)$ is des Vahejtnis vo seina Kantnzoi zua Kantnzoi vo am voiständign Graphn auf gleichvui Knotn, 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.

Schaug aa: Dilation.

Direkta Nachfoiga

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

Direkta Voagänga

In am grichteten Graphn hoasst a Knotn $u$ direkta Voagänga vo am Knotn $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 Knotn 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 Startknotn zum gleichn Zuiknotn san. A Menge vo Wegn hoasst disjunkt, wanns poarweis disjunkt san.

Existiarn fia jeds Poar $x,y$ vo Knotn $p$ disjunkte Weg vo $x$ noch $y$, so nennt ma an Graphn p-foch knotnzammahängend.

Distanz

De Distanz vo zwoa Knotn $v$ und $w$ in am Graphn (aa Obstand vo de Knotn 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 Knotn zu si sejm is (0).

Schaug aa: Distanzgraph.

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 Knotn in $G$ zuaordnet.

Schaug aa: Distanzgraph.

Dominationszoi

De Dominationszoi $\gamma (G)$ is de Mächtigkeit vo oana kloanstn dominiarendn Knotnmenge vo $G$.

Dominiarende Knotnmenge

A Knotnteimenge $X\subseteq V$ vo am Graphn $G=(V, E)$ hoasst dominiarend, wann jeda Knotn aus $V\setminus X$ zu am Knotn aus $X$ adjazent is.

Dreieck

A Dreieck is a Graph mit drei Knotn, 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 Knotn vo $G^*$ zuagordnet wead. Zwoa Knotn 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 Knotn 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$.

Schaug aa: Zentrum.

E

(zum Seitenofong)

Eckn

Schaug: Knotn.

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 Knotn is in am grichtetn Graphn de Ozoi vo seine direktn Vorgänga bezeichnet. Ma nennt des aa an negativn Grad vo am Knotn.

Schaug aa Grad, Ausgangsgrad, Nochborschoft und Grad in Graphn.

Eingangsmenge

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

Endknotn vo oana Kantn

Is $k=(x,y)$ a gerichtete Kantn, so bezeichnet ma $x$ ois ian Startknotn und $y$ ois ian Endknotn.

Ba ungrichtetn Kantn $k=\{x,y\}$ ko ma $x$ und $y$ sowoi ois Startknotn ois aa ois Endknotn bezeichnen. Do red ma in da Regl owa oafoch vo dena boadn „zu $k$ inzidentn Knotn“.

Eareichborkeitsmatrix

De Eareichborkeitsmatrix is a binäre Matrix und gibt im $n$-tn Schritt de gsamte Eareichborkeit vo de Knotn 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.

Schaug aa: 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 Knotn an grodn Grad hom, weshoib Eulersche Graphn noch eam benannt san. Ea hod emfois zoagt, dass in jedn semieulerschen Graphe entweda koa oda zwoa Knotn 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 Knotn an grodn Grad hod, a Eulertour existiat und in jedn Graphn, in dem zwoa Knotn ungrodn Grad hom, a Eulerweg existiat.

Schaug aa: 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 Kantnzug in am Graphn hoasst Eulerzug, wann a jede Kantn vom Graphn genau amoi enthoit. A Graph hoasst eulersch, wann a oan soichn Kantnzug besitzt.

Schaug aa: Eulerscher Graph.

Exzentrizität

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

Schaug aa: Radius, Duachmessa, Zentrum.

F

(zum Seitenofong)

Feabung

Schaug: Knotnfeabung, Kantnfeabung.

Feabungszoi

Schaug: Chromatische Zoi.

Faktor

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

Is $g(x) = p$ fia olle Knotn $x$, so red ma aa vo am $p$-Faktor.

Is $g(x) \ge a$ und $g(x) \le b$ fia olle Knotn $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 Knotn 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 Knotn $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 Knotn (aussa $s$ und $t$) meara aussefliassn ois einefliasst und ois, wos in an Knotn einefliasst, fliasst aa wieda ausse.

Fundamentalkroas

Zu am afspannendn Baam $T$ hoasst $W$ FundamentalKroas, fois a duach Dazuadoa vo oana Kantn zum Baam dazeigt wead.

Fundamentalschnitt

Wann $G$ zammahengend is. Zu am Spannendn Baam $T$ hoasst $S$ Fundamentalschnitt, fois $S$ ois Knotnmenge duach Weggalossa vo oana Kantn im Baam ois Zammahangskomponentn entsteht.

G

(zum Seitenofong)

Gordneta Baam

A gordneta Baam it a Wuazelbaam, wo fia de Kinda vo jedn Knotn a Ordnungsrelation definiat is. De Ordnung legt fest, wia de Nochfoiga vo am Knotn 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 Knoten ba untaschiedlichn Traversiarungsvafoan (preorder, inorder, postorder) duachlaffa wean.

Grichteta Graph

A Grichteta Graph (aa Digraph gnennt) is a Graph, wo grichtete Kantn enthoit.

Schaug aa: Typn vo Graphn in da Graphntheorie.

Grichtete Kantn

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

Schaug aa: 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 Knotn 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 Knoten oder oana Kantn zuagordnet wead.

Schaug aa: Gwicht, Knotngwicht, Kantngwicht.

Grad

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

Schaug aa: Eingangsgrad, Ausgangsgrad.

Gradfoige

Ois Gradfoige vo am Graphn $G = (V, E)$ mit dena Knotn $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 Knoten 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 Knotn, $E$ a Menge vo Kantn.

Jede Kantn hod je oan Ofangs- und Endknotn. Wean Ofangs- und Endknotn 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.

Schaug aa: Typn vo Graphn in da Graphntheorie, Hypergraph.

Graphisch

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

Graph mit Meahfochkanten

Wead de Fordarung aufgem, dass a Kantn duach iare zwoa Knoten festglegt is, so kenna zwoa Knotn 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 Knotn $v$ inam grichtetn Baam vasteht man an Vodda vom Vodda vo $v$.

Gitige Feabung

Schaug: Gitige Knotnfeabung.

Gitige Kantnfeabung

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

Guitige Knotnfeabung

A Knotnfeabung is gitig (oda echt), fois koa adjazentn Knotn existian, wo mit da gleichn Foab gfeabt san.

H

(zum Seitenofong)

Hamiltonobschluss

Da Hamiltonabschluss (oda Huin; $n$-Huin) vo am Graphn $G=(V, E)$ is da Obagraph (oda Supagraph) vo $G$ mit identischa Knotenmenge und zuasatzli iterativ einbautn Kantn, wo ned-adjazente (oda ned-benochboarte; ned-vabundene) Knotn 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 Knotn 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 Knotn vom Graphn enthoit.

Handschlag-Lemma

Des Handschlag-Lemma sogt, dass de Summe vo Knotngrad glei $2 \cdot |E(G)|$ is. (Jede Kantn drogt ba genau zwoa Knotn zum Knotengrad bei.) Daraus foigt, dass de Summe vo de Knotngrade stets grod is. Bsundas gibts imma a grode Ozoi vo Knotn, 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 Knotn vom Grad 2 in scho existiarendn Kantn heavoagenga.

Schaug aa: 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:

1. Fois $G$ koan Knotn vom Grad 2 besitzt (obgsegn vo isoliatn Knotn wo nua a Schleifn besitzen) so is $HU(G)=G$.
2. Wej oan Knotn $x$ vom Grad 2 (aussa isoliate Knotn mit oana Schleifn) mit dena boadn Nachborn $y$ und $z$ (aa $y=z$ is meglich)
3. Entfean $x$, dua dafia a Kantn vo $y$ noch $z$ dazua.
   Formal: $G \leftarrow (V\setminus \{x\},E\cup \{\{y,z\}\})$
4. geh zu 1

Schaug aa: Planara Graph.

Hozadssotz

In bipartiten Graphen $G$ mit Bipartition $\{A,B\}$ existiert genau dann eine Paarung $M$ der Kardinalität $|M| = |A|$ (die jeden Knoten 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 Kantn mea wia nur zwoa Knotn vabindn kenna. Kantn vo dera Foam nennt ma gwehnlich Hyperkantn. Mengentheoretisch betrochtet san Hypergraphen dessejbe wia Mengensysteme.

Schaug aa: Typn vo Graphn in da Graphtheorie.

Hyperkantn

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

Schaug aa: Typn vo Graphn in da Graphtheorie.

Hypohamiltonsch

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

I

(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 Knotn + 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 Knotenmenge vo $G$, so is da vo $I$ induziate Teigraph a Teigraph, wo duach de Entfeanung vo de Knotn aus $G$ entsteht, wo ned in $I$ liagn (miakts enk: bei Entfeanen vo am Knotn $k$ foin aa olle mit $k$ inzidentn Kantn wegga).

Anschaulich bedeidd des: Dea vo $I$ induziate Teigraph besteht aus dena Knotn aus $I$ und oin Kantn, wo in $G$ zwischn eana valaffa.

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

Innara Knotn

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

Inzidenz

Inzidenz bezeichnet a Beziahung zwischn Knotn und Kantn in am ungrichtetn Graphn. A Knotn 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 Startknotn und negativ inzident zu iam Endknotn.

Schaug aa: Adjazenz, Inzidenzmatrix, Nochborschoft und Grad in Graphn.

Inzidenzmatrix

A Inzidenzmatrix zu am Graph mit $n$ Knotn und $m$ Kantn is a $n \times m$-Matrix, ba dea wo de Zein mit de Knotn und de Spoitn mit dena Kantn identifiziat wean. Dazua nummeriat ma de Knotn vo 1 bis $n$ und de Kantn vo 1 bis $m$ duach und trogt in de Matrix de Beziahunga vo de Knotn 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 (Endknotn) und oamoi de −1 (Startknotn).

Schaug aa: Repräsentation vo Graphn im Computer.

Inzidenzrelation

Zua Definition sea oigmoana, nämle ungrichteta Graphn mit Schlingen (Kantn vo am Knotn zu si sejm) und paralleln Kantn (Meafochkantn) 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 Knotn vo de Kantn obhängt. Mittls 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 Knotn 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 Kantn 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 $M$, fois $x_i= \begin{cases} 0& \mbox{, falls } a_i \notin M \and {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 Untavektorraam vo $\mathbb{R}^m$, an Zyklenraam. De Menge vo de Fundamentalkroas san a Basis. Da Raam eagibt in direkta Summe mitm Kozyklenraam ganz $\mathbb{R}^m$

Isoliata Knotn

A isoliata Knotn is a Knotn 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

(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

(zum Seitenofong)

k-Baum

Ein ungerichteter Graph heißt k-Baum, wenn er wie folgt rekursiv erzeugbar ist:

• • Der vollständige Graph $K_k$ ist ein k-Baum.
  • Fügt man zu einem k-Baum $G$ einen neuen Knoten $v$ hinzu, indem man $v$ mit allen Knoten einer Clique der Größe k aus $G$ verbindet, so ist dieser neue Graph ebenfalls ein k-Baum.

Ein partieller $k$-Baum entsteht durch die Entfernung von Kanten aus einem $k$-Baum: Ist $G = (V, E)$ ein $k$-Baum, so ist $H = (V, F)$ mit $F \subseteq E$ ein partieller $k$-Baum.

Gelegentlich werden auch Bäume mit dem maximalen Grad $k$ als $k$-Bäume bezeichnet. Korrekter ist in diesem Fall die Bezeichnung $k$-närer Baum.

Kaktusgraph

Ein Graph $G$ heißt Kaktusgraph, wenn alle seine Kreise paarweise Kantendisjunkt sind (sich also höchstens gemeinsame Knoten teilen).

Ein Graph $G$ ist ein Kaktusgraph genau dann, wenn die Anzahl seiner Kreise seinem Index $\mu (G)$ entspricht.

Kante

Eine Kante ist ein Element der Kantenmenge eines Graphen. Die Kantenmenge eines Graphen $G$ wird meist mit $E(G)$ (für engl. edge) bezeichnet. Sie beschreibt, wie die Knoten der Knotenmenge des Graphen miteinander verbunden sind. Je nach Typ des Graphen unterscheiden sich die möglichen Formen von Kanten.

Siehe auch: Typen von Graphen in der Graphentheorie.

Vergleiche: Bogen bei Digraphen (gerichteten Graphen)

Kantenbewerteter Graph

Ein Kantenbewerteter Graph ist ein Graph $G$ mit einer Kantenbewertung $g$, welche formal eine Abbildung der Kantenmenge auf die reellen Zahlen ist. Die Kantenbewertungsfunktion $g$ bezeichnet man oft auch als Kostenfunktion oder Kantengewichtsfunktion.

Kantenbewertungen spielen häufig eine Rolle in Optimierungsproblemen, wie dem Travelling Salesman Problem, wobei die Bewertungen z. B. für Fahrtzeiten auf verschiedenen Straßen (Geschwindigkeitsbegrenzungen, Staus), Fahrtkosten (Maut, Benzinverbrauch) oder Streckenlänge steht.

Kantenfärbung

Ist $G=(V, E)$ ein ungerichteter Graph ohne Mehrfachkanten und $f$ eine Abbildung von $E$ in die Menge der natürlichen Zahlen $\mathbb{N}_0$, so nennt man $f$ eine Kantenfärbung von $G$.

Kantendisjunkte Wege

Zwei Wege heißen kantendisjunkt, wenn sie keine gemeinsamen Kanten haben. Im Gegensatz zu disjunkten Wegen dürfen kantendisjunkte Wege mehrere Knoten gemeinsam enthalten.

Kantenfärbungszahl

Siehe: Chromatischer Index.

Kantenfeld

Ein Kantenfeld ist eine Darstellungsart für gerichtete Graphen nach folgendem Schema:

$|V|, |E|, E_1,\ldots, E_{|E|}$

wobei $|V|$ die Anzahl der Knoten, $|E|$ die Anzahl der Kanten und $E_1, \ldots, E_{|E|}$ die Kanten sind mit $E_i = (v, w) \in E$.

Kantengraph

Der Kantengraph (engl. line graph) $L(G)$ eines Graphen $G$ entsteht folgendermaßen aus $G$:

• • Für jede Kante $k$ aus $G$ setze einen Knoten $k'$ in $L(G)$.
  • Füge eine Kante $\{k', l'\}$ in $L(G)$ genau dann ein, wenn die Kanten $k$ und $l$ in $G$ einen gemeinsamen Endknoten haben.

Kantenkontraktion

Ist $k$ eine Kante, die die Knoten $x$ und $y$ verbindet, dann ist die Kontraktion von $k$ eine „Verschmelzung“ von $x$ und $y$, d. h. $x$, $y$ und $k$ werden durch einen neuen Knoten $z$ ersetzt, der mit allen Nachbarn von $x$ und $y$ verbunden wird.

Haben $x$ und $y$ einen gemeinsamen Nachbarn $w$, so verlaufen im resultierenden Graphen parallele Kanten zwischen $z$ und $w$ oder allgemeiner: wenn zwischen $x$ und $w$ $n$ parallele Kanten und zwischen $y$ und $w$ $m$ parallele Kanten verlaufen, so verlaufen nach der Kontraktion von $k$ zwischen $z$ und $w$ genau $m+n$ parallele Kanten.

Kantenpanzyklische Graphen

Ein Graph heißt kantenpanzyklisch falls jede Kante auf einem Kreis der Länge $p$ liegt für alle $p \in \{1,2,\ldots,|V(G)|\}$. Kantenpanzyklische Graphen sind auch knotenpanzyklisch und damit auch panzyklisch.

Kantenüberdeckung

Eine Kantenüberdeckung in einem ungerichteten Graphen $G = (V, E)$ ist eine Menge $E' \subseteq E$ mit der Eigenschaft, dass jeder Knoten von $V$ in einer Kante aus $E'$ enthalten ist.

$E'$ ist Kantenüberdeckung in $G$ gdw. $\forall v \in V, \exists w \in E': v \in w$.

Kanten-Unterteilung

Eine Unterteilung einer Kante ist das Einfügen eines Knotens in die Kante

Formal: Ist $G=(V, E)$ ein Graph und $k=\{x, y\} \in E$, so entsteht $G'$ durch Unterteilung von $k$ als $G'=(V \cup \{z \notin V\}, E \setminus \{k\} \cup \{\{z,x\},\{z,y\}\})$. Die Voraussetzung $z\notin V$ ist für die formale Korrektheit notwendig.

Kantenzusammenhangszahl

Die Kantenzusammenhangszahl eines Graphen bezeichnet die Anzahl der Kanten, die man aus diesem entfernen muss, um den Zusammenhang aufzuheben.

Kind

Kind ist die Bezeichnung für einen direkten Nachfolger in einem Baum.

Knoten

Als Knoten oder Ecke bezeichnet man ein Element der Knotenmenge eines Graphen. Die Menge der Knoten eines Graphen $G$ wird meist mit $V(G)$ (für engl. vertex) bezeichnet. Graphen bestehen neben der Knotenmenge noch aus einer speziellen Kantenmenge, die beschreibt, wie die Knoten über Kanten verbunden sind.

Siehe auch: Typen von Graphen in der Graphentheorie.

Knotendisjunkte Wege

Zwei Wege heißen knotendisjunkt oder kreuzungsfrei, wenn sie keine gemeinsamen Knoten haben. Knotendisjunkte Wege sind immer auch kantendisjunkt. (Kantendisjunkte Wege sind aber nicht unbedingt knotendisjunkt!)

Knotenfärbung

Eine $p$-Knotenfärbung ist eine Abbildung der Knotenmenge auf die Menge $\{1, \ldots, p\}$ (also wird jedem Knoten eine von $p$ Zahlen oder „Farben“ zugewiesen).

Siehe auch: Gültige Knotenfärbung, Chromatische Zahl, Vier-Farben-Satz.

Knotenfärbungszahl

Siehe: Chromatische Zahl.

Knotenfeld

Ein Knotenfeld ist eine Darstellungsart für gerichtete Graphen mit folgendem Aufbau:

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

wobei $|V|$ die Anzahl der Knoten, $|E|$ die Anzahl der Kanten und $ag(V)$ Ausgangsgrad des Knotens sind.

Knotenpanzyklische Graphen

Ein Graph $G$ heißt knotenpanzyklisch, wenn jeder Knoten auf einem Kreis der Länge $p$ liegt, für alle $p \in \{1,2,\ldots,|V(G)|\}$.

Kantenpanzyklische Graphen sind knotenpanzyklisch, knotenpanzyklische Graphen sind panzyklisch.

Knotenüberdeckung

Als Knotenüberdeckung in einem ungerichteten Graphen bezeichnet man eine Teilmenge $U$ seiner Knoten, für die gilt, dass jede Kante wenigstens einen Knoten aus $U$ enthält.

$U$ ist Knotenüberdeckung in $G$ gdw. $\forall e \in E, \exists v \in U: v \in e$.

Siehe auch: Knotenüberdeckungen, Cliquen und stabile Mengen.

Knotniwadeckungszoi

Oiss Knotniwadeckungszoi vo am unerichteten Graphn wead de kloanste Zoi $k$ bezeichnet, fia de wo a Knotniwadeckung vo da Gress $k$ existiat.

Knotnzammahangszoi

De Knotenzusammenhangszoi (oft kuaz Zammahangszoi genannt) $\kappa (G)$ vo am Graphn $G$ is de kloanste Ozoi vo Knotn, dena eana Entfeanung an Zammahang zasteat.

Komplement

Schaug: Komplementeara Graph.

Komplementeara Graph

Da Komplementeare Graph $\overline{G}$ vo am Graphn $G$ hod de gleiche Knotenmenge wia $G$ und in $\overline{G}$ san zwoa Knotn $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.

Kozyklenraam

Is da Vektorraam vo olle duach Schnitte erzeigtn Inzidenzvektorn. Ea is Untaraam vom $\mathbb{R}^m$ und gibt in direkta Summe mitm Zyklenraam an ganzn Raam. 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 Knotn, wo bis auf an easchtn und letztn Knotn 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 Knotn 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 Knotn hom.

Kubischa Graph

A Graph is kubisch, foisa 3-regulea is.

L

(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

(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 Knotn 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$ existiert.

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.

Schaug aa: 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

Schaug aa: 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

(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 Huin)

Netzweak

A Netzweak is a gerichteta, kantnbeweateta Graph mit zwoa ausgezeichneten Knotn, vo da Quejn und da 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 Flisse betrocht. Moast is ma dobei am maximal meglichn s-t-Fluss interessiat, den ma beispuisweis mit am Edmonds-Karp-Algorithmus berechnen ko.

O

(zum Seitenofong)

Oafocha Graph

Ois oafocha Graph oda aa schlichta Graph wead a Graph ohne bsondare Strukturelemente wia Meafochkantn, orientiate Kantn, Schleifn, Knotn- oder 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

(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$.

Schaug aa: 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.

Schaug aa: 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 $p$-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 $p$-partit“ oda „$G$ is a $p$-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 gewejte 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 Kantn 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.

Schaug aa: chromatische Zoi, achromatische Zoi.

Q

(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.

Schaug aa: Senkn.

R

(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 $k$-regulea. A Wurzlbaam hoasst k-regulea, wenn olle Knotn mit Ausnohm vo de Bladdln an Ausgangsgrad $k$ hom.

Schaug aa: 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

(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)$.

SSchaug aa: 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. 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 beliebign 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.

Schaug aa: 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 vaschiedenen 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.

Schaug aa: 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.

Schaug aa: 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.

Schaug aa: 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 beliebign 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.

Schaug aa: Typn vo Graphn in da Graphntheorie.

T

(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).

Schaug aa: 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.

Schaug aa: 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.

Schaug aa: 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.

Schaug aa: Turniagraph

U

(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.

Schaug aa: 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.

Schaug aa: Grichtete Kantn, Typn vo Graphn in da Graphntheorie.

Ungrichteta Graph

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

Schaug aa: 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

(zum Seitenofong)

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 $M$-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 < v$.

Von am ungrichtetn Vagleichborkeitsgraphn redd ma, wann fia jede Kantn $(u, v) \in E$ guit: ($u < v$ oda $v < u$).

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. 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.

Schaug aa: 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 $p$-partita Graph is a p-partita Graph ba dem jeds Poar vo zwoa Knotn aus vaschiedenen Partitionsmengen adjazent is

• • An voiständign multipartitn Graphn mit $p$ Partitionsmengen, wo $n1,...,np$ Knotn enthoitn, bezeichnet ma mit $K_{n1, \ldots, np}$

Schaug aa: $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 Huin)

Vorweatskantn

Da Begriff Vorweatskantn hod genauso wia de Begriff Ruckweatskantn, Querkantn und Baamkantn a Bedeitung fia de 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

(zum Seitenofong)

Woid

A Woid is in da Graphntheorie a ungrichtets Graph ohne Kroas.

A Graph is dann a Woid, wann sei Index 0 is.

Schaug aa: Woid (Graphntheorie).

Weg

A Weg $W=(v_1, v_2, \ldots, v_p)$ is a Foign vo Knotn. Dabei miassn imma $v_i$ und $v_{i+1}$ adjazent sei fia olle $i=1,...,p-1$.

San olle Knotn poaweis vaschiedn, so red ma vo am Pfad.

In da Literadua wead a Pfad moastns ois Weg und a Weg ois Kantnzug bezeichnet.

Wegiwadeckung

A Menge vo disjunkte Wege in am gerichtetn Graphn $G$ mit da Oagnschoft, dass jeda Knotn vo $G$ af oan vo dena Wegn liegt, hoasst Wegiwadeckung.

Wuazl

A Wuazl is a Knotn, vo wo aus olle andan Knotn vom Graphn erreichbor san.

Schaug aa: Wuazlbaam.

Wuazlbaam

A Wuazlbaam is a Baam $B=(V, E)$ wo a Knotn ois Wuazl $w\in V$ auszeichnet is. Baam ohne Wuazl hoasst ma im Gegnsotz zu Wuazlbaam aa freie Baam. In da Literadua wead oft implizit a Wuazlbaam gmoant, wann oigmoa vo am Baaf de Red is. Wuazlbaam hom gegniwa frein Baam oanige bsondare Oagnschoftn:

• • Jeda Knotn $y$ af oam oafochn Pfad vo $w$ zu am andan Knotn $x$ hoasst Voagänga vo $x$.
  • Is $y$ a Voagänga vo $x$ und $x \neq y$, so hoasst $x$ Nochfoiga vo $y$.
  • Ein durch eine Kante verbundener Voagänga heißt auch Vater, $x$ heißt dann Sohn von $y$.
  • De Heh vo am Wuazlbaam is de maximale Läng vo am Pfad vo da Wuazl bis zu sm Blatt.

X

(zum Seitenofong)

Y

(zum Seitenofong)

Z

(zum Seitenofong)

Zentrum

Des Zentrum $Z(G)$ vo am Graphn $G$ is de Menge vo Knotn vo $G$, vo dena de Exzentrizität am Radius vo $G$ entspricht

Schaug aa: Duachmessa.

Zuaordnung

Schaug Poarung.

Zammahängenda Graph

A zammahängenda Graph is a Graph, wo nua aus oana Zammahongskomponentn besteht.

Zammahongskomponentn

A Zammahongskomponentn vo am ungrichteen Graphn is a maximale Teimenge vo seine Knotn, in dea zwischn je zwoa beliebign Knotn vo dera Menge mindastens a Weg existiat.

Zammahongszoi

Schaug: Knotnzammahongszoi.

Zyklischa Graph

A zyklischa Graph is a grichteta Graph, wo mindastens oan Zyklus enthoit.

Zyklomatische Zoi

Schaug: Index.

Zyklus

A Zyklus in oam Graphn is a Weg, wo im sejm Knotn ofongt und endet.

Eine Kante liegt genau dann auf einem Zyklus, wenn sie keine Brücke ist.

Schaug aa: 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.