Graf (matematik)

En graf er en matematisk abstraktion af et virkeligt system af enhver art, hvis objekter har parvise forbindelser. En graf som et matematisk objekt er en samling af to sæt - selve sættet af objekter, kaldet sættet af hjørner , og sættet af deres parvise forbindelser, kaldet sættet af kanter. Et element i et kantsæt er et par elementer i et toppunktsæt.

Grafer er meget udbredt i moderne videnskab og teknologi. De bruges både inden for naturvidenskab (fysik og kemi) og i samfundsvidenskab (for eksempel sociologi), men brugen af grafer har fået den største skala inden for datalogi og netværksteknologier.

Som det enkleste eksempel fra livet kan vi give et flyvediagram for et bestemt flyselskab, som er modelleret ved hjælp af en graf, hvor toppen af grafen er byer, og kanterne er flyve, der forbinder par af byer. Et bibliotekstræ i en computer er også en graf: drev, mapper og filer er hjørner, og kanterne viser indlejring af filer og mapper i mapper og drev [1] . Strukturen af Wikipedia er modelleret af en rettet graf , hvor artikler er grafens toppunkter, og hyperlinks er buer ( tematisk kort ).

Grafer er hovedobjektet for undersøgelse i grafteori .

Definitioner

Systemerne af den virkelige natur, der er modelleret af grafer, er meget forskellige, så der er forskellige typer grafer. Den enkleste abstraktion af systemer med elementer, der har parvise forbindelser, er en simpel graf .

Simpel graf

Definition. En simpel graf er en samling af to sæt - et ikke-tomt sæt og et sæt uordnede par af forskellige elementer i sættet . Et sæt kaldes et sæt af hjørner , et sæt kaldes et sæt kanter $G(V,E)$ $V$ $E$ $V$ $V$ $E$

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

det vil sige, at sættet består af 2-element undersæt af sættet . $E$ $V$

Relaterede termer

Grafteori har ikke en veletableret terminologi. Derfor kan nogle publikationer bruge andre udtryk end dem, der er anført nedenfor.

Et toppunkt (knudepunkt, punkt) ( eng. vertex, node, punkt ) af en graf er et element i et sæt af toppunkter ; $G$ $v\in V(G)$

En kant (linje) ( engelsk edge, line ) af en graf er et element i kantsættet , eller , hvor ; $G$ $e\in E(G)$ $e=\left\{v_{1},v_{2}\right\}$ $v_{1}\in V(G),\quad v_{2}\in V(G)$

Elementerne i en graf er dens toppunkter og kanter af grafen; $G$ $v\in V(G)$ $e\in E(G)$

Rækkefølgen ( engelsk orden ) af en graf er kardinalnummeret på sættet af toppunkter , eller med andre ord antallet af toppunkter; $G$ $n=|V(G)|$

Størrelsen ( engelsk størrelse ) af grafen er kardinalnummeret på sættet af kanter eller med andre ord antallet af kanter; $G$ $m=|E(G)|$

Et toppunkt falder sammen med en kant , hvis ; så siger de også, at der er kant ved ; $v$ $e$ $v\in e$ $e$ $v$

Endvertices (ender) ( eng. endvertices, ends ) er to toppunkter, der falder ind på en kant. Kanten forbinder ( engelsk joins ) sine endespidser;

Naboende (tilstødende) hjørner ( engelske neighbors, adjacent ) er sådanne spidser , og det eller med andre ord begge spidser er terminale for den ene kant; $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Tilstødende kanter ( engelske tilstødende kanter ) er kanter, der falder ind på ét toppunkt eller og - tilstødende; ${\displaystyle e_{1}=\venstre\{v,v_{1}\right\))$ $e_{2}=\venstre\{v,v_{2}\right\}$

Graden (valens) af et toppunkt ( eng. grad, valens ) er antallet af kanter, der falder ind på det. Graden af et toppunkt betegnes som ; $d(v)$

Et isoleret toppunkt ( eng. isoleret ) er et toppunkt med en grad , det vil sige, det er ikke enden af nogen kant; $d(v)=0$

Et hængende toppunkt (blad) ( eng. blad ) er et toppunkt med en grad , det vil sige, som er enden af præcis den ene kant. $d(v)=1$

Typisk er en graf afbildet som et diagram : knudepunkter - punkter, kanter - linjer.

Pseudograf

En pseudograf er en samling af to sæt - et ikke-tomt sæt og et sæt uordnede par af elementer i sættet . $G(V,E)$ $V$ $E$ $V$

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

Elementet er tilladt i sættet af kanter på pseudografen . $\left\{v,v\right\}\in E(G)$

En løkke er et element , der er en kant, hvis endespidser falder sammen. $e=\left\{v,v\right\}$

Med andre ord, hvis elementerne i sættet E kan være sløjfer, så kaldes grafen en pseudograf [2] .

Multigraf

En multigraf er en samling af to sæt - et ikke-tomt sæt og et multisæt af uordnede par af forskellige elementer i sættet . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

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

Flere kanter er identiske elementer i multisættet , det vil sige kanter, hvis endespidser falder sammen. $\left\{e,e,\dots ,e\right\}\in \mathbf {E}$

Med andre ord, hvis ikke et sæt, men en familie, det vil sige, hvis det indeholder de samme elementer, så kaldes sådanne elementer multiple edges, og grafen kaldes en multigraf [2] . $E$ $\mathbf {E}$

Pseudomultigraf

En pseudomultigraf er en samling af to sæt - et ikke-tomt sæt og et multisæt af uordnede par af elementer i sættet . $G(V,\mathbf {E} )$ $V$ $\mathbf {E}$ $V$

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

Med andre ord, hvis en familie, der indeholder de samme elementer (flere kanter) og kan indeholde sløjfer, så kaldes grafen en pseudo-multigraf [2] . $\mathbf {E}$ $\mathbf {E}$

Instrueret graf

Directed graph (digraph) ( eng. directed graph eller dirgaph ) er et sæt af to sæt - et ikke-tomt sæt og et sæt buer eller ordnede par af forskellige elementer i sættet $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øjre\},\prec \right\rangle \i E,\quad v\in V

sammen med to displays

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

hvor afbildningen tildeler hver bue dens indledende toppunkt (begyndelsen af buen) , og afbildningen tildeler hver bue dens endepunkt (enden af buen) . De siger, at buen fører fra til $init:E\rightarrow V$ $init(e)$ $ter:E\rightarrow V$ $ter(e)$ $e$ $init(e)$ $ter(e)$

Blandet graf

En blandet graf er en samling af tre sæt - et ikke-tomt sæt hjørner og et sæt buer eller ordnede par af forskellige elementer i sættet og et sæt kanter af uordnede par af forskellige elementer i sættet $G(V,E,U)$ $V$ $E$ $V$ $U$ $V$

G(V,E,U)=\venstre\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

sammen med to displays

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

Direkte og urettede grafer er særlige tilfælde af blandede grafer.

Isomorfe grafer

En graf kaldes isomorf i forhold til en graf, hvis der er en bijektion fra sættet af toppunkter i grafen til sættet af toppunkter i grafen , som har følgende egenskab: hvis grafen har en kant fra toppunkt til toppunkt , så grafen skal have en kant fra toppunkt til toppunkt og omvendt - hvis grafen har en kant fra toppunkt til toppunkt , så skal grafen have en kant fra toppunkt til toppunkt . I tilfælde af en rettet graf skal denne bijektion også bevare kantens orientering. I tilfælde af en vægtet graf skal bijektionen også bevare kantens vægt. $G$ $H$ $f$ $G$ $H$ $G$ $EN$ $B$ $H$ $f(A)$ $f(B)$ $H$ $EN$ $B$ $G$ $f^{-1}(A)$ $f^{-1}(B)$

Andre relaterede definitioner

En rute i en graf er en endelig sekvens af knudepunkter, hvor hvert knudepunkt (undtagen det sidste) er forbundet med det næste knudepunkt i sekvensen med en kant. En kæde er en rute uden gentagne kanter. En simpel sti er en sti uden gentagne hjørner (hvilket betyder, at der ikke er nogen gentagne kanter i en simpel sti).

En orienteret rute (eller sti ) i en digraf er en endelig sekvens af hjørner og buer, hvor hvert element falder sammen med det forrige og det næste.

En cyklus er en kæde, hvor første og sidste toppunkt falder sammen. I dette tilfælde er længden af stien (eller cyklus) antallet af dens konstituerende kanter . Bemærk, at hvis hjørnerne og er enderne af en eller anden kant, så er sekvensen ifølge denne definition en cyklus. For at undgå sådanne "degenererede" tilfælde introduceres følgende begreber. $u$ $v$ $(u,v,u)$

En sti (eller cykel) kaldes simpel , hvis kanterne på den ikke gentager sig; elementær , hvis den er enkel, og hjørnerne i den ikke gentages (med undtagelse af den indledende og sidste i tilfælde af en cyklus).

De enkleste egenskaber ved stier og cykler:

hver sti, der forbinder to hjørner, indeholder en elementær sti, der forbinder de samme to knudepunkter;
hver simpel ikke-elementær sti indeholder en elementær cyklus ;
hver simpel cyklus, der passerer gennem et eller andet toppunkt (eller kant), indeholder en elementær (under-)cyklus, der går gennem det samme toppunkt (eller kant);
en løkke er en elementær cyklus.

En binær relation på toppunktet af en graf, angivet som "der er en vej fra til ", er en ækvivalensrelation og opdeler derfor dette sæt i ækvivalensklasser, kaldet forbundne komponenter af grafen. Hvis en graf har præcis én tilsluttet komponent, så er grafen forbundet. På den tilsluttede komponent kan vi introducere begrebet afstand mellem toppunkter som minimumslængden af en sti, der forbinder disse toppunkter. $u$ $v$

Enhver maksimalt forbundet undergraf af en graf kaldes en forbundet komponent (eller blot en komponent) af grafen . Ordet "maksimum" betyder maksimum med hensyn til inklusion, dvs. ikke indeholdt i en forbundet undergraf med et stort antal elementer. $G$ $G$

En kant i en graf kaldes en bro, hvis dens fjernelse øger antallet af komponenter.

Yderligere karakteristika for grafer

Grafen hedder:

forbundet , hvis der for nogen hjørnereren sti fratil. $u$ $v$ $u$ $v$
stærkt forbundet eller retningsmæssigt forbundet , hvis det er orienteret, og der er en orienteret vej fra et hvilket som helst toppunkt til ethvert andet.
et træ, hvis det er forbundet og ikke indeholder ikke-trivielle cyklusser.
komplet , hvis nogen af dens to (forskellige, hvis sløjfer ikke er tilladt) hjørner er forbundet med en kant.
todelt , hvis dets toppunkter kan opdeles i to ikke-skærende delmængderogsåledes at enhver kant forbinder et toppunkt framed et toppunkt fra. $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$
k-partial, hvis dets toppunkter kan opdeles i ikke-skærende delmængder , , …, så der ikke er nogen kanter, der forbinder hjørnerne i samme delmængde. $k$ $V_{1}$ $V_{2}$ $V_{k}$
komplet bipartite , hvis hvert toppunkt i en delmængde er forbundet med en kant til hvert toppunkt i en anden delmængde.
plan , hvis grafen kan repræsenteres ved et diagram på et plan uden krydsende kanter.
vægtes , hvis hver kant af grafen er tildelt et bestemt tal, kaldet kantens vægt.
chordal , hvis grafen ikke indeholder inducerede cyklusser med en længde større end tre.

Det sker også:

Generalisering af begrebet en graf

En simpel graf er et endimensionelt forenklet kompleks .

Mere abstrakt kan en graf defineres som en tredobbelt , hvor og er nogle sæt ( hhv . hjørner og kanter ), og er en incidensfunktion (eller indfaldsfaktor ), der tildeler hver kant (ordnet eller uordnet) et par hjørner og fra (dens ender ). Særlige tilfælde af dette koncept er: $(V,E,\varphi)$ $V$ $E$ $\varphi$ $e\i E$ $u$ $v$ $V$

Euler-grafer - en graf, hvor der er en cyklisk Euler-sti ( Euler-cyklus );

Måder at repræsentere en graf i datalogi

Adjacency matrix

En tabel, hvor både kolonner og rækker svarer til grafens hjørner. I hver celle i denne matrix er der skrevet et tal, der bestemmer tilstedeværelsen af en forbindelse fra den øverste række til den øverste kolonne (eller omvendt).

Dette er den mest bekvemme måde at repræsentere tætte grafer på.

Ulempen er hukommelseskravene, som er direkte proportionale med kvadratet af antallet af toppunkter.

Todimensionelt array;
Matrix med huller;
Implicit indstilling (ved hjælp af en funktion).

Incidensmatrix

En tabel, hvor rækkerne svarer til grafens toppunkter, og kolonnerne svarer til grafens links (kanter). I en matrixcelle i skæringspunktet mellem en række og en kolonne skrives følgende: $jeg$ $j$

en i tilfælde af at forbindelsen "forlader" toppen ,

j

jeg

-1, hvis forbindelsen "kommer ind" i toppunktet, 0 i alle andre tilfælde (det vil sige, hvis forbindelsen er en sløjfe, eller forbindelsen ikke er indfaldende ved toppunktet)

Denne metode er ret rummelig (størrelsen er proportional med ) til opbevaring, så den bruges meget sjældent, i særlige tilfælde (for eksempel for hurtigt at finde cyklusser i en graf). $|V||E|$

Adjacency liste

En liste, hvor hvert hjørne af grafen svarer til en streng, der gemmer en liste over tilstødende hjørner. En sådan datastruktur er ikke en tabel i sædvanlig forstand, men er en "liste over lister".

Hukommelsesstørrelse: . $O(|V|+|E|)$

Dette er den mest bekvemme måde at repræsentere sparsomme grafer, såvel som når du implementerer grundlæggende grafgennemløbsalgoritmer i bredden eller dybden, hvor du hurtigt skal finde "naboerne" til det aktuelt viste toppunkt.

Liste over kanter

En liste, hvor hver kant af grafen svarer til en streng, der gemmer to hjørner, der falder ind på kanten.

Hukommelsesstørrelse: . $O(|E|)$

Dette er den mest kompakte måde at repræsentere grafer på, så den bruges ofte til ekstern lagring eller dataudveksling.

Beskrivelsessprog og grafprogrammer

Beskrivelsessprog

For at beskrive grafer, der er velegnede til maskinbearbejdning og samtidig bekvemme for menneskelig opfattelse, bruges flere standardiserede sprog, herunder:

DOT
GraphML
Trivielt grafformat
GML
GXL
XGMML
DGML

Byggeprogrammer

Der er udviklet en række kommercielle programmer til at bygge grafer, for eksempel er grafbygning grundlaget for ILOG applikationssoftwarepakker (siden 2009 ejet af IBM Corporation ), blandt andre programmer - GoView, Lassalle AddFlow, LEDA (der er en gratis udgave ).

Der er også et gratis grafprogram igraph og et gratis bibliotek kaldet Boost .

Visualiseringsprogrammer

Følgende softwareværktøjer bruges til at visualisere grafer :

Graphviz ( Eclipse Public License )
LION Graph Visualizer.
Grafanalysatoren er et russisksproget program med en enkel brugergrænseflade ( GNU LGPL ; kun Windows).
Gephi er en grafisk ramme til at repræsentere og studere grafer ( GNU GPL , CDDL ).
GraphX-biblioteket er et gratis .NET -bibliotek til beregning og tegning af grafer ved hjælp af WPF 4.0 .
MSAGL-biblioteket er et gratis bibliotek til .NET [3] .

Se også

Noter

↑ Burkatovskaya, 2014 , s. 3.
↑ 1 2 3 Burkatovskaya, 2014 , s. 6.
↑ Microsoft Automatic Graph Layout - Microsoft Research . research.microsoft.com. Hentet 15. november 2015. Arkiveret fra originalen 14. maj 2012. (ubestemt)

Litteratur

Burkatovskaya Yu. B. Teori om grafer. - Tomsk: Tomsk Polytekniske Universitets forlag, 2014. - T. 1. - 200 s.
Distel R. Grafteori. - Novosibirsk: Forlaget for Matematisk Institut. S. L. Sobolev SO RAN, 2002. - 336 s. - ISBN 5-86134-101-X.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Forelæsninger om grafteori. M.: Nauka, 1990. 384 s. (Udg. 2, rev. M.: URSS, 2009. 392 s.)
Kasyanov V.N., Evstigneev V.A. Grafer i programmering: bearbejdning, visualisering og anvendelse. - Sankt Petersborg. : BHV-Petersburg, 2003. - S. 1104. - ISBN 5-94157-184-4 .
Kirsanov M.N. Grafer i ahorn. — M. : Fizmatlit, 2007. — 168 s. - ISBN 978-5-9221-0745-7 .
Kormen T. M. et al., del VI. Algoritmer til at arbejde med grafer // Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M. : Williams, 2006. - S. 1296. - ISBN 0-07-013151-1 .
Ore O. Grafteori. — M .: Nauka, 1968. — 336 s.
Grafer // Encyklopædisk ordbog over en ung matematiker / Komp. A. P. Savin. - M . : Pædagogik , 1985. - S. 86 -88. — 352 s.
Salii VN, Bogomolov AM Algebraiske grundlag for teorien om diskrete systemer. - M .: Fysisk og matematisk litteratur, 1997. - ISBN 5-02-015033-9 .
Wilson R. Introduktion til grafteori. — M .: Mir, 1977. — 208 s.
Harari F. Grafteori. — M .: Mir, 1973.