Graf (matematik)

En graf är en matematisk abstraktion av ett verkligt system av vilken natur som helst, vars objekt har parvisa kopplingar. En graf som ett matematiskt objekt är en samling av två uppsättningar - själva uppsättningen av objekt, som kallas uppsättningen av hörn , och uppsättningen av deras parvisa anslutningar, som kallas uppsättningen av kanter. Ett element i en kantuppsättning är ett par element i en vertexuppsättning.

Grafer används ofta inom modern vetenskap och teknik. De används både inom naturvetenskap (fysik och kemi) och inom samhällsvetenskap (till exempel sociologi), men användningen av grafer har fått den största skalan inom datavetenskap och nätverksteknik.

Som det enklaste exemplet från livet kan vi ge ett flygdiagram för ett visst flygbolag, som är modellerat av en graf, där grafens hörn är städer och kanterna är flygningar som förbinder par av städer. Ett katalogträd i en dator är också en graf: enheter, mappar och filer är hörn, och kanterna visar kapsling av filer och mappar i mappar och enheter [1] . Wikipedias struktur är modellerad av en riktad graf , där artiklar är grafens hörn och hyperlänkar är bågar ( tematisk karta ).

Grafer är det huvudsakliga studieobjektet inom grafteori .

Definitioner

Systemen av verklig natur som modelleras av grafer är mycket olika, så det finns olika typer av grafer. Den enklaste abstraktionen av system med element som har parvisa anslutningar är en enkel graf .

Enkel graf

Definition. En enkel graf är en samling av två uppsättningar - en icke-tom uppsättning och en uppsättning oordnade par av olika element i uppsättningen . En uppsättning kallas en uppsättning av hörn , en uppsättning kallas en uppsättning av kanter $G(V,E)$ $V$ $E$ $V$ $V$ $E$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V,\quad \left\{v,v\ höger\}\notin E,\quad v\in V

det vill säga att mängden består av 2-elements delmängder av mängden . $E$ $V$

Relaterade termer

Grafteori har ingen väletablerad terminologi. Därför kan vissa publikationer använda andra termer än de som anges nedan.

En vertex (nod, punkt) ( eng. vertex, nod, point ) i en graf är ett element i en uppsättning av hörn ; $G$ $v\in V(G)$

En kant (linje) ( engelska edge, line ) av en graf är ett element i kantuppsättningen , eller , där ; $G$ $e\in E(G)$ $e=\left\{v_{1},v_{2}\right\}$ $v_{1}\in V(G),\quad v_{2}\in V(G)$

Elementen i en graf är dess hörn och kanter på grafen; $G$ $v\in V(G)$ $e\in E(G)$

Ordningen ( engelsk ordning ) för en graf är kardinalnumret för uppsättningen av hörn , eller, med andra ord, antalet hörn; $G$ $n=|V(G)|$

Storleken ( engelsk storlek ) på grafen är kardinalnumret för uppsättningen kanter eller, med andra ord, antalet kanter; $G$ $m=|E(G)|$

En vertex är infallande mot en kant om ; då säger de också att det finns en kant vid ; $v$ $e$ $v\in e$ $e$ $v$

Endvertices (ends) ( eng. endvertices, ends ) är två hörn som faller in mot en kant. Kanten förbinder ( engelska joins ) dess ändspetsar;

Närliggande (intilliggande) hörn ( engelska neighbors , adjacent ) är sådana hörn och att eller, med andra ord, båda hörnen är terminala för en kant; $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Intilliggande kanter ( engelska adjacent edges ) är kanter som faller in mot en vertex eller och - intill; $e_{1}=\left\{v,v_{1}\right\}$ $e_{2}=\left\{v,v_{2}\right\}$

Graden (valens) för en vertex ( eng. grad, valens ) är antalet kanter som faller in på den. Graden av en vertex betecknas som ; $d(v)$

En isolerad vertex ( eng. isolated ) är en vertex med en grad , det vill säga det är inte slutet på någon kant; $d(v)=0$

En hängande vertex (blad) ( eng. leaf ) är en vertex med en grad , det vill säga som är slutet på exakt en kant. $d(v)=1$

Vanligtvis är en graf avbildad som ett diagram : hörn - punkter, kanter - linjer.

Pseudograf

En pseudograf är en samling av två uppsättningar - en icke-tom uppsättning och en uppsättning oordnade par av element i uppsättningen . $G(V,E)$ $V$ $E$ $V$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V

Elementet är tillåtet i uppsättningen av kanter på pseudografen . $\left\{v,v\right\}\in E(G)$

En slinga är ett element som är en kant vars ändpunkter sammanfaller. $e=\left\{v,v\right\}$

Med andra ord, om elementen i mängden E kan vara loopar, kallas grafen en pseudograf [2] .

Multigraf

En multigraf är en samling av två uppsättningar - en icke-tom uppsättning och en multiuppsättning av oordnade par av olika element i uppsättningen . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times V\quad \left\{v,v\right\}\notin \mathbf {E} ,\quad v\in V

Flera kanter är identiska element i multisetet , det vill säga kanter vars ändhörn sammanfaller. $\left\{e,e,\dots ,e\right\}\in \mathbf {E}$

Med andra ord, om inte en mängd, utan en familj, det vill säga om den innehåller samma element, så kallas sådana element för flera kanter, och grafen kallas en multigraf [2] . $E$ $\mathbf {E}$

Pseudomultigraf

En pseudomultigraf är en samling av två uppsättningar - en icke-tom uppsättning och en multiuppsättning av oordnade par av element i uppsättningen . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

G(V,\mathbf {E} )=\left\langle V,\mathbf {E} \right\rangle ,\quad V\neq \varnothing ,\quad \mathbf {E} \subseteq V\times V

Med andra ord, om en familj som innehåller samma element (flera kanter) och kan innehålla loopar, kallas grafen en pseudo-multigraf [2] . $\mathbf {E}$ $\mathbf {E}$

Riktad graf

Riktad graf (digraph) ( eng. riktad graf eller dirgaph ) är en uppsättning av två uppsättningar - en icke-tom uppsättning och en uppsättning bågar eller ordnade par av olika element i uppsättningen $G(V,E)$ $V$ $E$ $V$

G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_{2}\ höger\},\prec \right\rangle \in E,\quad v\in V

tillsammans med två displayer

init:E\rightarrow V,\quad ter:E\rightarrow V

där mappningen tilldelar varje båge dess initiala vertex (bågens början) , och mappningen tilldelar varje båge dess ändpunkt (bågens ände) . De säger att bågen leder från till $init:E\rightarrow V$ $init(e)$ $ter:E\rightarrow V$ $ter(e)$ $e$ $init(e)$ $ter(e)$

Blandad graf

En blandad graf är en samling av tre uppsättningar - en icke-tom uppsättning av hörn , och en uppsättning bågar eller ordnade par av olika element i uppsättningen och en uppsättning kanter av oordnade par av olika element i uppsättningen $G(V,E,U)$ $V$ $E$ $V$ $U$ $V$

G(V,E,U)=\left\langle V,E,U\right\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_ {2}\right\},\prec \right\rangle \in E,\quad \left\{v_{3},v_{4}\right\}\in U,\quad v\in V

tillsammans med två displayer

init:E\rightarrow V,\quad ter:E\rightarrow V

Riktade och oriktade grafer är specialfall av blandade grafer.

Isomorfa grafer

En graf kallas isomorf till en graf om det finns en bijektion från uppsättningen av vertex i grafen till uppsättningen av vertex i grafen , som har följande egenskap: om grafen har en kant från vertex till vertex , då grafen måste ha en kant från vertex till vertex och vice versa - om grafen har en kant från vertex till vertex måste grafen ha en kant från vertex till vertex . I fallet med en riktad graf måste denna bijektion också bevara kantens orientering. I fallet med en viktad graf måste bijektionen också bevara kantens vikt. $G$ $H$ $f$ $G$ $H$ $G$ $A$ $B$ $H$ $fa)$ $f(B)$ $H$ $A$ $B$ $G$ $f^{-1}(A)$ $f^{-1}(B)$

Andra relaterade definitioner

En rutt i en graf är en ändlig sekvens av hörn där varje hörn (förutom den sista) är kopplad till nästa hörn i sekvensen med en kant. En kedja är en rutt utan upprepade kanter. En enkel bana är en bana utan upprepade hörn (vilket betyder att det inte finns några upprepade kanter i en enkel bana).

En orienterad rutt (eller bana ) i en digraf är en ändlig sekvens av hörn och bågar där varje element faller samman med föregående och nästa.

En cykel är en kedja där de första och sista hörnen sammanfaller. I det här fallet är längden på banan (eller cykeln) antalet kanter som består av . Observera att om hörnen och är ändarna på någon kant, är sekvensen enligt denna definition en cykel. För att undvika sådana "degenererade" fall introduceras följande begrepp. $u$ $v$ $(u,v,u)$

En stig (eller cykel) kallas enkel om kanterna på den inte upprepas; elementär om den är enkel och hörnen i den inte upprepas (med undantag för den initiala och sista i fallet med en cykel).

De enklaste egenskaperna hos stigar och cykler:

varje bana som förbinder två hörn innehåller en elementär bana som förbinder samma två hörn;
varje enkel icke-elementär väg innehåller en elementär cykel ;
varje enkel cykel som passerar genom någon vertex (eller kant) innehåller en elementär (del-)cykel som passerar genom samma vertex (eller kant);
en slinga är en elementär cykel.

En binär relation på vertexuppsättningen av en graf, angiven som "det finns en väg från till ", är en ekvivalensrelation och delar därför upp denna uppsättning i ekvivalensklasser, kallade sammankopplade komponenter i grafen. Om en graf har exakt en ansluten komponent, är grafen ansluten. På den anslutna komponenten kan vi introducera begreppet avstånd mellan hörn som den minsta längden på en väg som förbinder dessa hörn. $u$ $v$

Varje maximalt ansluten subgraf i en graf kallas en ansluten komponent (eller helt enkelt en komponent) av grafen . Ordet "maximum" betyder maximalt med avseende på inkludering, det vill säga inte ingår i en sammankopplad subgraf med ett stort antal element. $G$ $G$

En kant i en graf kallas en brygga om dess borttagning ökar antalet komponenter.

Ytterligare egenskaper hos grafer

Grafen heter:

ansluten om det för några hörnfinnsen väg fråntill. $u$ $v$ $u$ $v$
starkt ansluten eller riktningsansluten om den är orienterad och det finns en orienterad bana från vilken vertex som helst till vilken som helst.
ett träd om det är anslutet och inte innehåller icke-triviala cykler.
komplett om någon av dess två (olika, om loopar inte är tillåtna) hörn är förbundna med en kant.
tvådelad om dess hörn kan delas in i två icke-korsande delmängderochså att valfri kant förbinder en vertex frånmed en vertex från. $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$
k-partial om dess hörn kan delas in i icke-korsande delmängder , , ..., så att det inte finns några kanter som förbinder hörnen i samma delmängd. $k$ $V_{1}$ $V_{2}$ $V_{k}$
komplett bipartite , om varje vertex i en delmängd är ansluten med en kant till varje vertex i en annan delmängd.
plan , om grafen kan representeras av ett diagram på ett plan utan korsande kanter.
viktas om varje kant av grafen tilldelas ett visst nummer, som kallas kantens vikt.
kordal om grafen inte innehåller inducerade cykler med längd större än tre.

Det händer också:

Generalisering av begreppet graf

En enkel graf är ett endimensionellt förenklat komplex .

Mer abstrakt kan en graf definieras som en trippel , där och är några uppsättningar ( av hörn respektive kanter ), och är en infallsfunktion (eller incidentor ) som tilldelar varje kant (ordnad eller oordning) ett par hörn och från (dess ändar ). Särskilda fall av detta koncept är: $(V,E,\varphi )$ $V$ $E$ $\varphi$ $e\in E$ $u$ $v$ $V$

Euler-grafer - en graf där det finns en cyklisk Euler-bana ( Eulercykel );

Sätt att representera en graf inom datavetenskap

Adjacency matris

En tabell där både kolumner och rader motsvarar grafens hörn. I varje cell i denna matris skrivs ett nummer som bestämmer närvaron av en anslutning från den översta raden till den översta kolumnen (eller vice versa).

Detta är det bekvämaste sättet att representera täta grafer.

Nackdelen är minneskraven, som är direkt proportionella mot kvadraten på antalet hörn.

Tvådimensionell array;
Matris med luckor;
Implicit inställning (med en funktion).

Incidensmatris

En tabell där raderna motsvarar grafens hörn och kolumnerna motsvarar länkarna (kanterna) på grafen. I en matriscell i skärningspunkten mellan en rad och en kolumn skrivs följande: $i$ $j$

ett om anslutningen "lämnar" toppen ,

j

i

-1, om anslutningen "går in" i vertexet, 0 i alla andra fall (det vill säga om anslutningen är en slinga eller om anslutningen inte är infallande vid vertex)

Denna metod är ganska rymlig (storleken är proportionell mot ) för lagring, så den används mycket sällan, i speciella fall (till exempel för att snabbt hitta cykler i en graf). $|V||E|$

Adjacency list

En lista där varje hörn i grafen motsvarar en sträng som lagrar en lista med angränsande hörn. En sådan datastruktur är inte en tabell i vanlig mening, utan är en "lista med listor".

Minnesstorlek: . $O(|V|+|E|)$

Detta är det bekvämaste sättet att representera glesa grafer, såväl som när du implementerar grundläggande grafgenomgångsalgoritmer i bredd eller djup, där du snabbt behöver få tag på "grannarna" till det aktuella hörnet.

Lista över kanter

En lista där varje kant av grafen motsvarar en sträng som lagrar två hörn som faller in mot kanten.

Minnesstorlek: . $O(|E|)$

Detta är det mest kompakta sättet att representera grafer, så det används ofta för extern lagring eller datautbyte.

Beskrivningsspråk och grafprogram

Beskrivningsspråk

För att beskriva grafer som är lämpliga för maskinell bearbetning och samtidigt bekväma för mänsklig perception, används flera standardiserade språk, inklusive:

PUNKT
GraphML
Trivialt grafformat
GML
GXL
XGMML
DGML

Bygga program

En serie kommersiella program för att bygga grafer har utvecklats, till exempel är grafbyggnad basen för ILOG- applikationsmjukvarupaket (sedan 2009 ägt av IBM Corporation ), bland andra program - GoView, Lassalle AddFlow, LEDA (det finns en gratisutgåva ).

Det finns också ett gratis grafprogram igraph och ett gratis bibliotek som heter Boost .

Visualiseringsprogram

Följande mjukvaruverktyg används för att visualisera grafer :

Graphviz ( Eclipse Public License )
LION Graph Visualizer.
Grafanalysatorn är ett ryskspråkigt program med ett enkelt användargränssnitt ( GNU LGPL ; endast Windows).
Gephi är ett grafiskt ramverk för att representera och studera grafer ( GNU GPL , CDDL ).
GraphX-biblioteket är ett gratis .NET -bibliotek för att beräkna och rita grafer med WPF 4.0 .
MSAGL-biblioteket är ett gratis bibliotek för .NET [3] .

Se även

Anteckningar

↑ Burkatovskaya, 2014 , sid. 3.
↑ 1 2 3 Burkatovskaya, 2014 , sid. 6.
↑ Microsoft Automatic Graph Layout - Microsoft Research . research.microsoft.com. Hämtad 15 november 2015. Arkiverad från originalet 14 maj 2012. (obestämd)

Litteratur

Burkatovskaya Yu. B. Theory of Graphs. - Tomsk: Tomsk Polytechnic Universitys förlag, 2014. - T. 1. - 200 sid.
Distel R. Graph Theory. - Novosibirsk: Matematikinstitutets förlag. S. L. Sobolev SO RAN, 2002. - 336 sid. - ISBN 5-86134-101-X.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Föreläsningar om grafteori. M.: Nauka, 1990. 384 sid. (Utg. 2, rev. M.: URSS, 2009. 392 s.)
Kasyanov V.N., Evstigneev V.A. Grafer i programmering: bearbetning, visualisering och tillämpning. - St Petersburg. : BHV-Petersburg, 2003. - S. 1104. - ISBN 5-94157-184-4 .
Kirsanov M.N. Grafer i lönn. — M. : Fizmatlit, 2007. — 168 sid. - ISBN 978-5-9221-0745-7 .
Kormen T. M. et al, del VI. Algoritmer för att arbeta med grafer // Algoritmer: konstruktion och analys = Introduktion till algoritmer. - 2:a uppl. - M. : Williams, 2006. - S. 1296. - ISBN 0-07-013151-1 .
Ore O. Grafteori. — M .: Nauka, 1968. — 336 sid.
Grafer // Encyclopedic Dictionary of a Young Mathematician / Comp. A.P. Savin. - M . : Pedagogy , 1985. - S. 86 -88. — 352 sid.
Salii VN, Bogomolov AM Algebraiska grunder för teorin om diskreta system. - M .: Fysisk och matematisk litteratur, 1997. - ISBN 5-02-015033-9 .
Wilson R. Introduktion till grafteori. — M .: Mir, 1977. — 208 sid.
Harari F. Grafteori. — M .: Mir, 1973.