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 Werkeln

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


Inhoitsvazoachnis 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 Werkeln

Achromatische Zoi Werkeln

De achromatische Zoi   vo am Graphn   is de gresste Zoi  , fia de   a gitige und voistendige Knupffeabung mit   Forbm hod.
Schau aaa: chromatische Zoi, pseudo-achromatische Zoi.

Adjazenz Werkeln

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 Werkeln

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

Adjazenzmatrix Werkeln

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 Werkeln

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 Werkeln

Schaug: Vabesserungspfad.

Artikulation Werkeln

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

Augmentierender Pfad Werkeln

Schaug: Vabesserungspfad.

Ausgangsgrad Werkeln

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 Werkeln

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

Automorphismus Werkeln

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 Werkeln

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

B Werkeln

(zum Seitenofong)

Bandbroadn Werkeln

De Bandbroadn (engl. bandwidth, schaug aa Bandbroadn) vo am endlichn, schlichtn, ungrichtetn Graphn is wia foigt definiat: Sei   a eineindeitige Nummariarung vo de Knupf. Dann bezeichnet   de Bandbroadn in Bezug af   und   de Bandbroadn vom Graphn  .
De Eamiddlung vo da Bandweitn is oans vo de wenign Probleme, wo aa fia Baam NP-voiständig is.

Baam Werkeln

A Baam is a zammahängenda Graph, wo koane Zykln enthoit. Genaua:   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 Werkeln

Schaug: Vorweatsvabinda.

Bipartition Werkeln

A Bipartition is a 2-Partition.

Bipartita Graph Werkeln

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 Werkeln

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 Werkeln

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

Blockgraph Werkeln

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

Bogn Werkeln

Schaug: Grichtete Kantn.

Bruggn Werkeln

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

C Werkeln

(zum Seitnofang)

Chordala Graph Werkeln

Schaug: Trianguliata Graph.

Chromatische Zoi Werkeln

De chromatische Zoi (aa Knupffeabungszoi oda kuaz Feabungszoi, sejtn aa Forbzoi gnennt) vo am Graphn is de kloanste Zoi  , fia de da Graph ae zualässige Knupffearbung mit   Forbm besitzt. Des is gleizeiti as de kloanste natialiche Zoi, fia de des chromatische Polynom   is.
Schau aaa: Partition, Feabung, achromatische Zoi, pseudo-achromatische Zoi.

Chromatischa Index Werkeln

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

Clique Werkeln

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

Cliquenproblem Werkeln

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

Cliquenzoi Werkeln

De Cliquenzoi   vo am ungrichtetn Graphn   is de gresste Zoi  , für de   eine Clique der Größe   besitzt.
Schau aaa: Cliquenproblem.

D Werkeln

(zum Seitenofong)

Diafn Werkeln

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 Werkeln

De Dichtn   vo am oafochn Graphn   is des Vahejtnis vo seina Vabindazoi zua Vabindazoi vo am voiständign Graphn af gleichvui Knupf, des hoasst:
 

Digraph Werkeln

Schaug: grichteta Graph.

Dilation Werkeln

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 Werkeln

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

Direkta Voagänga Werkeln

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

Disjunkte Weg Werkeln

Zwoa Weg   und   hoassn disjunkt, fois olle Knupf aus   vaschiedn vo dena aus   san. Haifig losst ma zua, dass   und  , 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   vo Knupf   disjunkte Weg vo   noch  , so nennt ma an Graphn p-foch knupfzammahängend.

Distanz Werkeln

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

Distanzgraph Werkeln

A Distanzgraph   vo am Graphn   is da voiständige kantngwichtetn Graphn iwa  , wo jeda Kantn de Distanz vo de zuaghearign Knupf in   zuaordnet.

Dominationszoi Werkeln

De Dominationszoi   is de Mächtigkeit vo oana kloanstn dominiarendn Knupfmenge vo  .

Dominiarende Knupfmenge Werkeln

A Knupfteimenge   vo am Graphn   hoasst dominiarend, wann jeda Knupf aus   zu am Knupf aus   adjazent is.

Dreieck Werkeln

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

Dreiecksfreia Graph Werkeln

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

Duala Graph Werkeln

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

Duachmessa Werkeln

Da Duachmessa   vo am Graphn   is des Maximum vo de Exzentrizitätn vo de Knupf vo  
Fia olle Graphn   guit  . Dabei is   da Radius vo  .
Schau aaa: Zentrum.

E Werkeln

(zum Seitenofong)

Eckn Werkeln

Schaug: Knupf.

Einbettung Werkeln

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

Eingangsgrad Werkeln

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 Werkeln

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

Endknupf vo oana Kantn Werkeln

Is   a gerichtete Kantn, so bezeichnet ma   ois ian Startknupf und   ois ian Endknupf.
Ba ungrichtetn Vabinda   ko ma   und   sowoi ois Startknupf ois aa ois Endknupf bezeichnen. Do red ma in da Regl owa oafoch vo dena boadn „zu   inzidentn Knupf“.

Eareichborkeitsmatrix Werkeln

De Eareichborkeitsmatrix is a binäre Matrix und gibt im  -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 Werkeln

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 Werkeln

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 Werkeln

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 Werkeln

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

Eulerweg Werkeln

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

Eulerzug Werkeln

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 Werkeln

De Exzentrizität   vo am Knupf   is de Distanz (de Läng vo am kiazestn Weg) zu am Knupf  , wo maximaln Obstand vo   hod.
Schau aaa: Radius, Duachmessa, Zentrum.

F Werkeln

(zum Seitenofong)

Feabung Werkeln

Schaug: Knupffeabung, Kantnfeabung.

Feabungszoi Werkeln

Schaug: Chromatische Zoi.

Faktor Werkeln

Is   a Graph und   a Obbuidung vo de Knupf af natialiche Zoin, so is an  -Faktor   a Teigraph vo  , mit   (oiso nur Kantn wean entfernt) und jeda Knupf   hod in   an Grad  .
Is   fia olle Knupf  , so red ma aa vo am  -Faktor.
Is   und   fia olle Knupf  , so red ma vo am  -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   und   oan Graphn   konstruian ko, wo genau dann oan 1-Faktor besitzt, wann   oan  -Faktor besitzt. Des is de Definition vo oana Reduktion im Sinn vo da theoretischen Informatik. Wei umgekeat 1-Faktorn Spezialfoi vo  -Faktorn san, is des  -Faktorproblem äquivalent zum 1-Faktorproblem.

Faktor-kritisch Werkeln

A Graph   mit   hoasst faktor-kritisch, wann duach des Wegganehma vo am Knupf a perfekte Poarung megli wead.

Fobzoi Werkeln

Schaug: Chromatische Zoi.

Flächn Werkeln

Flächn vo am planarn Graphen nennt man des Gebiet vo da Ebene (oda vo oana Flächn in  ), wo duach a Kantn vo am planarn Graphn, dea wo in da Ebene (bzw. auf da Flächn) einbedd is, eigrahmt wead.

Fluss Werkeln

A Fluss zu am grichtetn Graphn und Kantnkapazitetn it a Funktion   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   (aussa fia de Quejn   und de Senkn  ) gejtn, dass de Summe vo de Flisse af de einefiarendn Kantn gleich da Summe vo de Flisse af de aussefiarendn Kantn is.
Formal:  
Anschaulich: aus koam Knupf (aussa   und  ) meara aussefliassn ois einefliasst und ois, wos in an Knupf einefliasst, fliasst aa wieda ausse.

Fundamentalkroas Werkeln

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

Fundamentalschnitt Werkeln

Wann   zammahengend is. Zu am Spannendn Baam   hoasst   Fundamentalschnitt, fois   ois Knupfmenge duach Weggalossa vo oana Kantn im Baam ois Zammahangskomponentn entsteht.

G Werkeln

(zum Seitenofong)

Gordneta Baam Werkeln

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 Werkeln

A Grichteta Graph (aa Digraph gnennt) is a Graph, wo grichtete Vabinda enthoit.
Schau aaa: Typn vo Graphn in da Graphntheorie.

Grichtete Kantn Werkeln

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 Werkeln

Schaug: Grichteta Zyklus.

Grist Werkeln

A Grist is a Teigraph vo am Graphn  , wo olle Knupf aus   enthoit. Is   zammahengend, so is des Grist zglei a Spannbaam. Is   ned zammahengend, so bezeichnet ma des entstehende Grist aa ois Spannwoid oda afspannenda Woid.

Gwicht Werkeln

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

Grad Werkeln

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

Gradfoige Werkeln

Ois Gradfoige vo am Graphn   mit dena Knupf   bezeichnet ma de Foige natialicha Zoin  , wejche jeweil an Grad vo oanzalnen Knupf ogem, d. h.   fia olle  . A soichane Foige vo natialichn Zoin hoasst a graphisch, wann echt mindastns oa Graph existiat, wo de Gradfoige hod.

Graph Werkeln

A Graph is a Tupl  .   is a nedlaare Menge vo Knupf,   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 Werkeln

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

Graph mit Meahfochvabinda Werkeln

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 Werkeln

Schaug: Maximale Clique.

Gresste Poarung Werkeln

Schaug: Maximale Poarung.

Gresstes Matching Werkeln

Schaug: Maximale Poarung.

Grossvodda Werkeln

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

Gitige Feabung Werkeln

Schaug: Gitige Knupffeabung.

Gitige Kantnfeabung Werkeln

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

Guitige Knupffeabung Werkeln

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

H Werkeln

(zum Seitenofong)

Hamiltonobschluss Werkeln

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

Hamiltonscha Graph Werkeln

A Graph hoasst hamiltonsch, fois a oan Hamiltonkroas besitzt.

Hamiltonkroas Werkeln

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

Hamiltonkroas Problem Werkeln

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 Werkeln

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

Handschlag-Lemma Werkeln

Des Handschlag-Lemma sogt, dass de Summe vo Knupfgrad glei   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 Werkeln

De Hehn vo am Wuazlbaam is de maximal aftretende Tiafn.

Homöomorphie Werkeln

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 Werkeln

Da Homeomorphie-Uasprung   vo am Graphn   is da kloanste Graph, zu dem   homeomorph is. Ma berechnet   mit am foigenden Algorithmus:
  1. Fois   koan Knupf vom Grad 2 besitzt (obgsegn vo isoliatn Knupf wo nua a Schleifn besitzen) so is  .
  2. Wej oan Knupf   vom Grad 2 (aussa isoliate Knupf mit oana Schleifn) mit dena boadn Nachborn   und   (aa   is meglich)
  3. Entfean  , dua dafia a Kantn vo   noch   dazua.
    Formal:  
  4. geh zu 1
Schau aaa: Planara Graph.

Hozadssotz Werkeln

In bipartiten Graphen   mit Bipartition   existiad genau dann eine Paarung   der Kardinalität   (de jeden Knupf aus   überdeckt), falls für jede Teilmenge   von   gilt, dass ihre Nachbarschaft mindestens so groß ist wie   selbst:
 
Siehe auch: Paarung.

Hypergraph Werkeln

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 Werkeln

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 Werkeln

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

I Werkeln

(zum Seitenofong)

Index Werkeln

Da Index vo am Graphn is definiat ois:
  (Ozoi vo de Kantn − Ozoi vo de Knupf + Ozoi vo de Zammahangskomponentn)
    • Fia olle Graphn   is   und   is genau dann a Woid, wann   guit
    • Da Index vo am Graphn   is stets kloanagleich da Ozoi vo seine Kroas und   is genau dann a Kaktusgraph, wann sein Index da Ozoi vo de Kroas in   entspricht

Induziata Teigraph Werkeln

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

Innara Knupf Werkeln

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 Werkeln

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 Werkeln

A Inzidenzmatrix zu am Graph mit   Knupf und   Kantn is a  -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   und de Kantn vo 1 bis   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 Werkeln

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   mit   mit   ned aus, denn do miasstn z. B. in   Duplikate erlaubt sein. Ma fiaht dahea a Inzidenzrelation ein und benennt de Elemente aus   mit am eindeitigen Nama  , 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  , d. h. zu jedn Knupf wead fia jede Kantn, wo eam beriat, a Element   mit   und   in   afgenumma. Schlingen wean somit iwa jeweis a Element vo da Inzidenzrelation, zwoa parallele Vabinda iwa via Elemente vo da Inzidenzrelation eindeitig repräsentiat.

Inzidenzvektor Werkeln

Zu oana beliabig vorgeban Nummeriarung vo de Kantn   is a Element   a Inzidenzvektor zua (gwichtetn) Kantnmenge  , fois   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  , an Zyklenram. De Menge vo de Fundamentalkroas san a Basis. Da Ram eagibt in direkta Summe mitm Kozyklenram ganz  

Isoliata Knupf Werkeln

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

Isomorphie Werkeln

Zwoa Graphn   und   hoassn isomorph, fois a bijektive Obbuidung   existiat, sodass fia olle   guit:   genau dann, wann  

J Werkeln

(zum Seitenofong)

Jordankuavn Werkeln

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 Werkeln

(zum Seitenofong)

k-Baam Werkeln

A ungrichteta Graph hoasst k-Baam, wen a wia foigt rekursiv eazeigbor is:
    • Da voiständige Graph   is a k-Baam.
    • Gibt ma zua an k-Baam   an neien Knupf   dazua, indem ma   mid oin Knupf vo oana Clique vo da Gräss k aus   vabindt, so is da neie Graph emfois a k-Baam.
A partiella  -Baam entstäht duach de Entfernung vo Vabinda aus am  -Baam: Is   a  -Baam, so it   mit   a partiella  -Baam.
Gelegentli wean aa Baam mitm maximalen Grad   ois  -Baam bezoachnet. Korrekta is in dem Foi de Bezoachnung  -nära Baam.

Kaktusgraph Werkeln

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

Kindl Werkeln

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

Knupf Werkeln

A Knupf (dt. Knoten oda Ecke) is a Element vom Knupfhaffa (Knotenmenge) vo am Graphn. Dea Haffa vo de Knupf vo am Graphn   hoasst ma moast mit   (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 Werkeln

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 Werkeln

Eine  -Knupffärbung (dt. Knotenfärbung) is a Obbuidl vo am Knupfhaffa af den Haffa (dt. Menge)   (oiso wead an jedn Knupf oane vo <matth>p</math> Zoin oda „Forbn“ zuagwiesn).

Knupffeabungszoi Werkeln

Schaug: Kromatische Zoi.

Knupffejd Werkeln

A Knupffejd (dt. Knotenfeld) is a Dorstejungsart fia grichtade Graphn mid foigandn Afbau:
 
wobei   de Ozoi vo de Knupf,   de Ozoi vo de Vabinda und   Ausgangsgrad vom Knupf san.

Knupfpanzyklische Graphn Werkeln

A Graph   hoasst knupfnpanzyklisch, wen jeda Knupf af am Kroas vo da Läng   liegt, fia olle  .
Vabindapanzyklische Graphn san knupfpanzyklisch, knupfpanzyklische Graphn san panzyklisch.

Knupfibadeckung Werkeln

Ois Knupfibadeckung in am ungrichtadn Graphn hoasst ma an Teihaffa   vo seine Knupf, fia de wo guit, dass jeda Vabinda wenigstns oan Knupf aus   enthoid.
  is a Knupfibadeckung in   gdw.  .

Knupfibadeckungszoi Werkeln

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

Knupfzammahangszoi Werkeln

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

Komplement Werkeln

Schaug: Komplementeara Graph.

Komplementeara Graph Werkeln

Da Komplementeare Graph   vo am Graphn   hod de gleiche Knupfmenge wia   und in   san zwoa Knupf   und   genau dann Adjazent, wenn se s in   ned san (  hod oisdann genau de Kantn, wo   ned hod).
Als Sejmkomplementea bezeichnet ma Graphn, wo isomorph zu iam Komplementean Graphn san.

Komplementgraph Werkeln

Schaug: Komplementeara Graph.

Kozyklenram Werkeln

Is da Vektorram vo olle duach Schnitte erzeigtn Inzidenzvektorn. Ea is Untaram vom   und gibt in direkta Summe mitm Zyklenram an ganzn Ram. A Basis is imma duach de Fundamentalschnitt gem.

Kroas Werkeln

A Kroas   is a Foign vo Knupf, wo bis auf an easchtn und letztn Knupf poarweis vaschiedn san, wobei sowoi   und   fia olle   ois aa   und   adjazent sein miassn.
Enthoit a Kroas olle Knupf vom Graphn, so nennt man Hamiltonkroas.
A Graph wo nua aus am Kroas (vo da Leng  ) bsteht bezeichnet ma mit  .

Kreizungsfreie Weg Werkeln

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

Kubischa Graph Werkeln

A Graph is kubisch, foisa 3-regulea is.

L Werkeln

(zum Seitenofong)

Leng vo am Kroas Werkeln

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

Leng vo am Pfad Werkeln

Schaug: Leng vo am Weg.

Leng vo am Weg Werkeln

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

Leng vo am Zyklus Werkeln

Schaug: Leng vo am Kroas.

Linegraph Werkeln

Schaug: Kantngraph.

M Werkeln

(zum Seitenofong)

Matching Werkeln

Schaug: Poarung.

Matchingzoi Werkeln

Schaug: Poarungszoi.

Maximale Clique Werkeln

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

Maximale Poarung Werkeln

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

Maximals Matching Werkeln

Schaug: Maximale Poarung.

Maximalgrad Werkeln

Da Maximalgrad   vo am Graphn   is de gresste Zoi  , fia de in   a Knotn vom Grad   existiad.
Entspricht da Maximalgrad am Minimalgrad, so redd ma vo am regulearn Graphn.

Meafochkantn Werkeln

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 Werkeln

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

Metrischa Graph Werkeln

A Metrischa Graph is a kantnbewerteta Graph, wo de Dreiecksungleichung erfuit, d. h. san  , so guit stets  , wobei   de Bewertung vo da Kantn   is.
Intuitiv formuliat: da Weg vo   iwa   noch   deaf ned kiaza sein, ois da direkte Weg vo   noch  .
Distanzgraphn san stets Metrisch.

Metrisches Traveling-Salesman-Problem Werkeln

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 Werkeln

Da Minimalgrad   vo am Graphn   is de kloanste Zoi  , fia de in   an Knotn vom Grad   existiat.
Entspricht dar Minimalgrad am Maximalgrad, so spricht ma vo am regulearn Graphn.

Minor Werkeln

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

Multigraph Werkeln

Mit Multigraph bezeichnet ma an Graphn mit Meafochkantn

Multikantn Werkeln

Schaug: Meafochkantn.

N Werkeln

(zum Seitenofong)

Nochboar Werkeln

A Knotn   is Nochboar vo am Knotn   genau daun, wann   oiso wanns duach a Kantn vabundn san.
Bei grichtetn Graphn untascheidet ma positive - und negative Nochboarn. Genau daun, wann   a grichtete Kantn vo   nach   fiat, nennt ma   positivn Nochboarn vo   und   negativn Nochboarn vo  .

Nochboarschoft Werkeln

De Nochboarschoft   vo am Knotn   is de Menge vo seine Nochboarn.
Bei grichtetn Graphn untascheidet ma de positive Nachboarschaft   (de Menge vo de Knotn, zu dena a grichtete Kantn vo   aus fiat) und de negative Nochboarschoft   (de Menge vo de Knotn, vo dena aus a gerichtete Kantn zu   fiat)
De Obgschlossene Nochboarschaft is   oiso nix ondas ois de Nochboarschoft vo  , zu dea   sejm hinzuagfigt woan is. (analog san   und   definiat)

Nochboarschoftslistn Werkeln

Schaug: Adjazenzlistn.

Nochboarschoftsmatrix Werkeln

Schaug: Adjazenzmatrix.

Nochfoiga Werkeln

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

Nochfoigamenge Werkeln

De Menge vo oin Nochfoigan vo am Knotn  . Oisdann olle in am Graphn vo   duach an Pfad erreichboarn Knotn.
Formei:   mit   ('schaug aa: Transitive Huin)

Netzweak Werkeln

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 Werkeln

(zum Seitenofong)

Oafocha Graph Werkeln

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 Werkeln

A oafocha Kroas in am schlichtn, ungrichteten Graphn   is a Kroas, wo jedn Knotn   genau a Moi enthoid.

Oafocha Pfad Werkeln

A oafocha Pfad in am schlichtn, ungrichtetn Graphn   is a Pfad, wo jedn Knotn   genau a Moi enthoid.

Obagraph Werkeln

A Graph   is a Obagraph vo am Graphn  , wann   a Teigraph vo   is.

Obstand Werkeln

Schaug: Distanz.

Ongl Werkeln

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

Ordnung vo am Baam Werkeln

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

P Werkeln

(zum Seitenofong)

Poarung Werkeln

A Poarung (aa Matching, Zuaordnung oda unobhängige Kantnmenge) in am ungrichteten Graphn   is a Menge   mit da Eigenschoft, dass koane zwoa Kantn aus   in   duach an gmoasamen Knotn vabundn san:
  is unobhängi in   gdw.  .
Schau aaa: perfekte Poarung, maximale Poarung.

Poarungszoi Werkeln

De Poarungszoi is de vo oana maximein Poarung.

Panzyklische Graphn Werkeln

A Graph hoasst panzyklisch wann a fia olle   oan Kroas vo da Läng   besitzt.
Insbesondas san panzyklische Graphn damit hamiltonsch.
Schau aaa: Knotnpanzyklische Graphn, Kantnpanzyklische Graphn.

Parallele Kantn Werkeln

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

Partieller k-Baum Werkeln

Schaug: k-Baam.

Partition Werkeln

  is a Graph is A Zalegung (Partition) vo da Knotnmenge   in   disjunkte Teimengen   hoasst  -Partition, fois koane adjazentn Eckn in am gmoasamen   liegn. (Oschauli hoasst des: olle Kantn valaffen zwischn dena Teimengen, koane innahoib vo oana vo de Teimengen.)
    • Besitzt a Graph   a  -Partition, so soggdma aa „  is  -partit“ oda „  is a  -partiter Graph“.
    • De chromatische Zoi vo   is des kloanste  , sodass   a  -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 Werkeln

Ois perfekte Eliminationsordnung bezeichnet ma a Knotnreihenfoig   vom Graphn  , so dass fia jedn Graphn mit da (duach Eliminiarung vo de Knotn   bis  ) eingschränktn Knotnmenge   guit:   is simplizial in  . Jeda (in Bezug af de gewejde Ordnung) „kloanste“ Knotn in   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 Werkeln

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

Perfektes Matching Werkeln

Schaug Perfekte Poarung.

Pfad Werkeln

A Pfad   is a Foign vo Knotn, mit poarweise vaschiedanen Knotn, wobei imma   und   adjazent sein müssen für alle  .
Enthoit   olle Knotn vo  , so nennt man   an Hamiltonpfad.
Fordat ma ned, dass de Knotn vo   poarweis vaschieden san, so redd ma vo am Weg.

Planara Graph Werkeln

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   odar   ois Minor hod.
Schaug: Planarer Graph.

Pseudo-achromatische Zoi Werkeln

De pseudo-achromatische Zoi   vo am Graphn   is de gresste Zoi  , fia de wo   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 Werkeln

(zum Seitenofong)

Quejn Werkeln

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 Werkeln

(zum Seitenofong)

Rand Werkeln

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

Reguleara Graph Werkeln

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  , so hoasst ma den  -regulea. A Wurzlbaam hoasst k-regulea, wenn olle Knotn mit Ausnohm vo de Bladdln an Ausgangsgrad   hom.
Schau aaa: Nochboarschoft und Grad in Graphn.

Radius Werkeln

Da Radius   vo am Graphn   is des Minimum vo de Exzentrizitätn vo de Knotn vo  .
Fia olle Graphn   guit  , wo   da Duachmessa vo   is.
De Knotn, vo dena de Exzentrizität am Radius entsprecha duat, buidn des Zentrum vo  .

Ruckweatskantn Werkeln

Schaug: Vorweatskantn.

S Werkeln

(zum Seitenofong)

Sotz vom Hall Werkeln

Schaug: Hozadssotz.

Schleifn Werkeln

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  .
SSchau aaa: Meafochschleifn.

Schleifnfreia Graph Werkeln

Schaug: Schleifenlosa Graph.

Schleifnlosa Graph Werkeln

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

Schlinge Werkeln

Schaug: Schleifn.

Schnitt Werkeln

A Zalegung (oda Partition)   vo da Knotnmenge   vo am Graphn in zwoa nichtlaare Teimengen   und   mit   und   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 Werkeln

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

Schwoche Zammahangskomponentn Werkeln

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 Werkeln

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

Semieulerscha Graph Werkeln

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 Werkeln

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 Werkeln

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 Werkeln

  is a endlicha, ungrichteta, schlichta Graph. A Knotnmenge   hoasst dann Separator fia zwoa ned bednochboarte Knotn   gdw.   und   in   in vaschiednan Zammahangskomponentn liegn.

Simpliziala Knotn Werkeln

A Knotn   vom Graphn   hoasst ma simplizial', wann a gmoasam mit oi seine Nachboarn a Cliquen, d. h. an voiständign Teigraphen in   buidd.

Spannbaam Werkeln

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 Werkeln

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

Spannwoid Werkeln

Schaug Grist.

Stabile Menge Werkeln

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 Werkeln

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 Werkeln

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

Stoarke Zammahangskomponentn Werkeln

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 Werkeln

Is   a grichtete Kantn, so bezeichnet mn   ois ian Startknotn und   ois ian Endknotn.
Bei ungerichtetn Kantn   ko ma   und   sowoi ois Startknotn ois aa ois Endknotn bezeichna. Do redd ma in da Regl owa oafoch vo de zwoa „zu   inzidentn Knotn“.

Stern Werkeln

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 Werkeln

Schaug: Teigraph.

Symmetrischa Graph Werkeln

A symmetrischa Graph is a grichteta Graph, wo mit jeda Kantn   aa de Kantn   enthoit.
Schau aaa: Typn vo Graphn in da Graphntheorie.

T Werkeln

(zum Seitenofong)

Taillenweitn Werkeln

De Taillenweitn   vo am Graphn   is de Läng vo am kiazestn Kroas in  . Is   a Woid (hod oisdann koane Kroas) so setzt ma  .

Teigraph Werkeln

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

Topologische Ordnung Werkeln

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

Topologische Sortiarung Werkeln

Schaug: Topologische Ordnung bzw. Topologische Sortiarung.

Travelling Salesman Problem Werkeln

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 Werkeln

A endlicha, schlichta und ungrichteta Graph hoasst trianguliat oda aa chordal, wann a koane induziatn Kroas   mit   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 Werkeln

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

Triviala Kroas Werkeln

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

Triviala Zyklus Werkeln

De Foign   vo Knotn, wo aus nua oam Knotn besteht,eafuit de Definition vo am Zyklus

Turniagraph Werkeln

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

U Werkeln

(zum Seitenofong)

Umfang Werkeln

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

Unobhängige Knotnmenge Werkeln

A unobhängige Knotnmenge in am ungrichteten Graphn   is a Menge   mit da Oagnschoft, dass koane zwoa Knotn aus   in   duach a Kantn vabunden san:
  is unobhängig in   gdw.  .

Unobhängige Kantnmenge Werkeln

Schaug Poarung.

Unobhängige Menge Werkeln

Schaug: Stabile Menge.

Unobhängigkeitszoi Werkeln

Schaug: Stabilitätszoi.

Unendlicha Graph Werkeln

A unendlicha Graph is a Graph, vo dem sei Knotnzoi unendle os.
Schau aaa: Unendlicha Graph

Ungrichtete Kantn Werkeln

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 Werkeln

A ungrichteta Graph is an Graph, wo koane grichtetn Kantn enthoit.
Schau aaa: Typn vo Graphn in da Graphntheorie.

Uniforma Hypergraph Werkeln

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

Universala Knotn Werkeln

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

Untabaam Werkeln

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

Untagraph Werkeln

Schaug: Teigraph.

Unzammahängenda Graph Werkeln

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

V Werkeln

(zum Seitenofong)

Vabinda Werkeln

A Vabinda is a Element vom Vabindahaffa vo am Graphn. Da Vabindahaffa vo am Graphn   wead moast mit   (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 Werkeln

A vabindabeweatada Graph is a Graph   mit ama Vabindabeweatung  , de wo formal a Obuidl vom Vabindahaffa af de reelln Zoin is. De Vabindabeweatungsfunktion   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. B. fia Fohrtzeidn af vaschiednann Stroßn (Gschwindigkeitsbegrenzunga, Staus), Fohrtkosten (Maut, Benzinvabrauch) oda Strecknläng stäht.

Vabindafärbung Werkeln

Is   a ungrichteda Graph ohne Meafochvabinda und   a vo   in de Haffa vo de natialichn Zoin  , so nennt ma   a Vabindafärbung vo  .

Vabindadisjunkte Wege Werkeln

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

Vabindafärbungszoi Werkeln

Schaug: Chromatischa Index.

Vabindafejd Werkeln

A Vabindafejd is a Doastejungsoart fia grichtade Graphn nocham foigendn Schema:
 
wobei   de Ozoi vo de Knupf,   de Ozoi vo de Vabinda und   de Vabinda san mid  .

Vabindagraph Werkeln

Da Vabindagraph (engl. line graph)   vo am Graphn   entstähd so aus  :
    • Fia jedn Vabinda   aus   setz an Knupf   in  .
    • Bau an Vabinda   in   genau nacha ei, wen de Vabinda   und   in   an gmoasama Endknupf hom.

Vabindakontraktion Werkeln

Is   a Vabinda, dea wo de Knupf   und   vabindet, nacha is de Kontraktion vo   a „Vaschmejzung“ vo   und  , d. h.  ,   und   wean duach an neien Knupf   dasezt, dea wo mid oin Nochbarn vo   und   vabundn wead.
Hom   und   an gmoasama Nochbarn  , so valaffa im resultiarendn Graphn parallele Vabinda zwischn   und   oda oigmoana: wen zwischn   und     parallele Vabinda und zwischn   und     parallele Vabinda valaffa, so valaffa noch da Kontraktion vo   zwischen   und   genau   parallele Vabinda.

Vabindapanzyklische Graphn Werkeln

A Graph hoasst vabindapanzyklisch fois jeda Vabinda af am Kroas vo da Läng   liegt fia olle  . Vabindanzyklische Graphn san aa knupfnpanzyklisch und so aa panzyklisch.

Vabindaibadeckung Werkeln

A Vabindaibadeckung in am ungrichtadn Grapen   is a Haffa   mid da Oagnschoft, dass a jeda Knupf vo   in am Vabinda aus   enthoidn is.
  is a Vabindaibadeckung in   gdw.  .

Vabinda-Untateilung Werkeln

A Untateilung vo am Vabinda is as Eibaun vo am Knupf.
Formal: It   a Graph und  , so entstäd   duach Untateilung vo   ois  . De Voraussezung   is fia de formale Korrektheid noudwendi.

Vabindazammahangszoi Werkeln

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

Valenz Werkeln

Schaug: Grad.

Valenzsequenz Werkeln

Schaug: Gradfoign.

Vodda Werkeln

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

Vabesserungspfad Werkeln

Is   a Graph und   a Poarung in  , dann is a Vabesserungspfad (aa  -alterniarenda Pfad) a Pfad  , wo obwechselnd Kantn aus   und Kantn aus   enthoit, wobei an boadn Endn Knotn liagn, de wo mit koana Kantn aus   inzidian (oiso san aa de boadn Endkantn vo   aus  ).
A soicha Pfad hoasst Vabesserungspfad, wei ma a Poarung   mit   dahoidn ko, indem ma de Kantn vo  , wo in   liagn aus   entfeant und dafia de andan Kantn vo   zu   dazudoa.
Satz vo Berge (1957): A Poarung is genau dann maximal, wanns koan Vabesserungspfad gibt.

Vagleichborkeitsgraph Werkeln

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

Voiständige Knotenfeabung Werkeln

A voiständige Knotenfeabung is a Knotenfeabung, ba dea wo fia jeds Poar   vo Foarbm a Kantn   existiat, sodass   mit   und   mit   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.
Schau aaa: chromatische Zoi, achromatische Zoi, pseudo-achromatische Zoi.

Voiständige Zuaordnung Werkeln

Schaug: Perfekte Poarung.

Voiständiga Graph Werkeln

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   Knotn bezeichnet ma mit  
A voiständiga  -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   Partitionsmengen, wo   Knotn enthoitn, bezeichnet ma mit  
Schau aaa:   und   in Charakterisarung vo planarn Graphn.

Vorgänga Werkeln

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

Vorgängamenge Werkeln

De Menge vo oin Vorgängan vo am Knotn  . Oisdann olle Knotn in am Graphn vo dena   duach an Pfad eareicht wean ko.
Formei:   mit   wobei   de Knotnmenge,   de Menge vo de Pfade und   de Vorgängamenge is, ('schaug aa: Transitive Huin)

Vorweatskantn Werkeln

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 Werkeln

(zum Seitenofong)

Woid Werkeln

A Woid is in da Graphntheorie a ungrichtets Graph ohne Kroas.
A Graph is dann a Woid, wann sei Index 0 is.
Schau aaa: Woid (Graphntheorie).

Weg Werkeln

A Weg   is a Foign vo Knotn. Dabei miassn imma   und   adjazent sei fia olle  .
San olle Knotn poaweis vaschiedn, so red ma vo am Pfad.
In da Literatua wead a Pfad moastns ois Weg und a Weg ois Vabindazug bezeichnet.

Wegiwadeckung Werkeln

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

Wuazl Werkeln

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

Wuazlbaam Werkeln

A Wuazlbaam is a Baam   wo a Knotn ois Wuazl   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   af oam oafochn Pfad vo   zu am andan Knotn   hoasst Voagänga vo  .
    • Is   a Voagänga vo   und  , so hoasst   Nochfoiga vo  .
    • A duach an Vabinda vabundena Voagänga hoasst aa Voda,   hoasst nacha Sohn vo  .
    • De Häh vo am Wuazlbaam is de maximale Läng vo am Pfad vo da Wuazl bis zu sm Blatt.

X Werkeln

(zum Seitenofong)

Y Werkeln

(zum Seitenofong)

Z Werkeln

(zum Seitenofong)

Zentrum Werkeln

Des Zentrum   vo am Graphn   is de Menge vo Knotn vo  , vo dena de Exzentrizität am Radius vo   entspricht
Schau aaa: Duachmessa.

Zuaordnung Werkeln

Schaug Poarung.

Zammahängenda Graph Werkeln

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

Zammahongskomponentn Werkeln

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

Zammahongszoi Werkeln

Schaug: Knotnzammahongszoi.

Zyklischa Graph Werkeln

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

Zyklomatische Zoi Werkeln

Schaug: Index.

Zyklus Werkeln

A Zyklus in oam Graphn is a Weg, wo im sejm Knotn ofongt und endet.
A Vabinda liegt genau nacha af am Zyklus, wen sie koa Bruckn ist.
Schau aaa: Wege, Pfade, Zyklen und Kroas in Graphn.

Zyklenraum Werkeln

A Zyklenraum is da Vektorraum vo oin duach (gwichtete) Kroas beschriebanen Inzidenzvektorn. Ea is a Untaverktorraum vo  . In direkta Summe mitm Kozyklenraum eagibt a an ganzn Raum. De Fundamentalkroas san a Basis.
→ Dea Artikl basiad auf ara frein Ibasetzung vom säim Artike in da Wikipedia af Deitsch in da Version vom 14. Meaz 2010.