Grafikon (matematika)

A gráf egy tetszőleges természetű valós rendszer matematikai absztrakciója , amelynek objektumai páronkénti kapcsolatban állnak egymással. A gráf mint matematikai objektum két halmaz gyűjteménye - maguknak az objektumoknak a halmaza, amelyet csúcskészletnek neveznek , és páronkénti kapcsolataik halmaza, amelyet élek halmazának neveznek. Egy élhalmaz eleme egy csúcshalmaz elempárja.

A grafikonokat széles körben használják a modern tudomány és technológia területén. Mind a természettudományokban (fizika és kémia), mind a társadalomtudományokban (például szociológia) használják őket, de a gráfok használata a számítástechnikában és a hálózati technológiákban érte el a legnagyobb léptéket.

Az életből a legegyszerűbb példaként megadhatjuk egy adott légitársaság repülési diagramját, amelyet egy gráf modellez, ahol a gráf csúcsai városok, élei pedig várospárokat összekötő járatok. A számítógépben található könyvtárfa egyben gráf is: a meghajtók, mappák és fájlok csúcsok, az élek pedig a fájlok és mappák egymásba ágyazását mutatják mappákban és meghajtókban [1] . A Wikipédia szerkezetét irányított gráf modellezi , amelyben a cikkek a gráf csúcsai, a hiperhivatkozások pedig ívek ( tematikus térkép ).

A gráfelmélet tanulmányozásának fő tárgya a grafikon .

Definíciók

A valós természet gráfokkal modellezett rendszerei igen változatosak, ezért a gráfok különböző típusai léteznek. A páronkénti kapcsolattal rendelkező elemekből álló rendszerek legegyszerűbb absztrakciója egy egyszerű gráf .

Egyszerű grafikon

Meghatározás. Az egyszerű gráf két halmaz gyűjteménye - egy nem üres halmaz és a halmaz különböző elemeinek rendezetlen párjainak halmaza . A halmazt csúcsok halmazának , a halmazt élek halmazának nevezzük $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\ jobb\}\notin E,\quad v\in V

vagyis a halmaz a halmaz 2 elemű részhalmazaiból áll . $E$ $V$

Kapcsolódó kifejezések

A gráfelméletnek nincs jól bevált terminológiája. Ezért egyes kiadványok az alábbiakban felsoroltaktól eltérő kifejezéseket is használhatnak.

A gráf csúcsa (csomópont, pont) ( eng. vertex, node, point ) egy csúcshalmaz eleme ; $G$ $v\in V(G)$

A gráf éle (vonala) ( angol él, vonal ) az élhalmaz eleme , vagy , ahol ; $G$ $e\in E(G)$ $e=\left\{v_{1},v_{2}\right\}$ $v_{1}\in V(G),\quad v_{2}\in V(G)$

A gráf elemei a gráf csúcsai és élei ; $G$ $v\in V(G)$ $e\in E(G)$

A gráf sorrendje ( angolul order ) a csúcsok halmazának kardinális száma , vagy más szóval a csúcsok száma; $G$ $n=|V(G)|$

A gráf mérete ( angolul size ) az élek halmazának kardinális száma vagy más szóval az élek száma; $G$ $m=|E(G)|$

Egy csúcs incidens egy élre , ha ; akkor azt is mondják, hogy a -nál él van ; $v$ $e$ $v\in e$ $e$ $v$

A végcsúcsok (végek) ( eng. endvertices, ends ) egy élre eső két csúcs. Az él összeköti ( angolul joins ) a végpontjait;

A szomszédos (szomszédos) csúcsok ( angolul szomszédok, szomszédos ) olyan csúcsok , amelyek vagy más szóval mindkét csúcs egy élhez terminális; $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

A szomszédos élek ( angolul szomszédos élek ) olyan élek, amelyek egy csúcsba esnek, vagy - szomszédosak; ${\displaystyle e_{1}=\left\{v,v_{1}\right\))$ $e_{2}=\left\{v,v_{2}\right\}$

Egy csúcs foka (valenciája) ( eng. fokozat, vegyérték ) a rá eső élek száma. Egy csúcs fokát a következővel jelöljük ; $d(v)$

Az izolált csúcs ( eng. isolated ) olyan csúcs, amelynek foka van, vagyis nem egy él vége; $d(v)=0$

A függő csúcs (leaf) ( eng. leaf ) egy olyan csúcs, amelynek foka van, vagyis pontosan egy élnek a vége. $d(v)=1$

A gráfokat általában diagramként ábrázolják : csúcsok - pontok, élek - vonalak.

Pszeudográf

Az pszeudográf két halmaz gyűjteménye – egy nem üres halmaz és a halmaz rendezetlen elempárjainak halmaza . $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

Az elem megengedett a pszeudográf éleinek halmazában . $\left\{v,v\right\}\in E(G)$

A hurok olyan elem , amely egy él, amelynek végpontjai egybeesnek. $e=\left\{v,v\right\}$

Más szóval, ha az E halmaz elemei lehetnek hurkok, akkor a gráfot pszeudográfnak nevezzük [2] .

Multigráf

A multigráf két halmaz gyűjteménye – egy nem üres halmaz és a halmaz különböző elemeinek rendezetlen párjainak multihalmaza . $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

A több él a multihalmaz azonos eleme , vagyis olyan él, amelynek végpontjai egybeesnek. $\left\{e,e,\dots ,e\right\}\in \mathbf {E}$

Vagyis ha nem halmaz, hanem család, vagyis ha ugyanazokat az elemeket tartalmazza, akkor az ilyen elemeket többszörös élnek, a gráfot pedig multigráfnak [2] . $E$ $\mathbf {E}$

Pszeudomultigráf

A pszeudomultigráf két halmaz gyűjteménye – egy nem üres halmaz és a halmaz rendezetlen elempárjainak több halmaza . $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

Más szóval, ha egy család ugyanazokat az elemeket (több élt) tartalmazza és tartalmazhat hurkokat, akkor a gráfot pszeudo-multigráfnak nevezzük [2] . $\mathbf {E}$ $\mathbf {E}$

Irányított gráf

Az irányított gráf (digráf) ( eng. irányított gráf vagy dirgaph ) két halmaz halmaza - egy nem üres halmaz és a halmaz különböző elemeiből álló ívek vagy rendezett párok halmaza $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}\ jobb\},\prec \jobbra\rangle \in E,\quad v\in V

két kijelzővel együtt

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

ahol a leképezés minden ívhez hozzárendeli a kezdeti csúcsát (az ív kezdetét) , és a leképezés minden ívhez hozzárendeli a végcsúcsot (az ív végét) . Azt mondják, hogy az ív tól ig vezet $init:E\rightarrow V$ $init(e)$ $ter:E\rightarrow V$ $ter(e)$ $e$ $init(e)$ $ter(e)$

Vegyes gráf

A vegyes gráf három halmaz gyűjteménye - csúcsok nem üres halmaza , és a halmaz különböző elemeiből álló ívek vagy rendezett párok halmaza , valamint a halmaz különböző elemeiből álló rendezetlen párok éleinek halmaza. $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

két kijelzővel együtt

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

Az irányított és irányítatlan gráfok a vegyes gráfok speciális esetei.

Izomorf gráfok

Egy gráfot akkor nevezünk izomorf gráfnak, ha a gráf csúcsainak halmazától a gráf csúcshalmazához bijekció van , amelynek a következő tulajdonsága van: ha a gráfnak van egy éle a csúcstól a csúcsig , akkor a gráf élnek kell lennie a csúcstól a csúcsig és fordítva - ha a gráfnak van egy éle a csúcstól a csúcsig , akkor a gráfnak csúcstól csúcsig kell élnie . Irányított gráf esetén ennek a bijekciónak meg kell őriznie az él orientációját is. Súlyozott gráf esetén a bijekciónak meg kell őriznie az él súlyát is. $G$ $H$ $f$ $G$ $H$ $G$ $A$ $B$ $H$ $f(A)$ $f(B)$ $H$ $A$ $B$ $G$ $f^{-1}(A)$ $f^{-1}(B)$

Egyéb kapcsolódó definíciók

Az útvonal a gráfban egy véges csúcssorozat, amelyben minden csúcs (az utolsó kivételével) egy éllel kapcsolódik a sorozat következő csúcsához. A lánc ismétlődő élek nélküli útvonal. Az egyszerű útvonal egy ismétlődő csúcsok nélküli útvonal (ami azt jelenti, hogy az egyszerű útvonalban nincsenek ismétlődő élek).

Az orientált útvonal (vagy útvonal ) egy digráfban csúcsok és ívek véges sorozata, amelyben minden elem az előzőre és a következőre esik.

A ciklus olyan lánc, amelyben az első és az utolsó csúcs egybeesik. Ebben az esetben az út (vagy ciklus) hossza az alkotó éleinek száma . Figyeljük meg, hogy ha a és csúcsok valamelyik él végei, akkor e definíció szerint a sorozat egy ciklus. Az ilyen "elfajzott" esetek elkerülése érdekében a következő fogalmakat vezetjük be. $u$ $v$ $(u,v,u)$

Egy utat (vagy ciklust) egyszerűnek nevezünk , ha a benne lévő élek nem ismétlődnek; elemi , ha egyszerű, és a benne lévő csúcsok nem ismétlődnek (ciklus esetén a kezdő és a záró kivételével).

Az utak és ciklusok legegyszerűbb tulajdonságai:

minden két csúcsot összekötő út tartalmaz egy elemi utat, amely ugyanazt a két csúcsot köti össze;
minden egyszerű nem elemi út tartalmaz egy elemi ciklust ;
minden egyes csúcson (vagy élen) áthaladó egyszerű ciklus tartalmaz egy elemi (al)ciklust, amely ugyanazon a csúcson (vagy élen) halad át;
a hurok elemi ciklus.

A gráf csúcshalmazán lévő bináris reláció , amelyet úgy adunk meg, hogy "van egy út innentől -ig ", egy ekvivalenciareláció , és ezért ezt a halmazt ekvivalenciaosztályokba osztja fel, amelyeket a gráf összekapcsolt összetevőinek neveznek. Ha egy gráfnak pontosan egy összefüggő komponense van, akkor a gráf össze van kötve. Az összekapcsolt komponensen bevezethetjük a csúcsok közötti távolság fogalmát, mint az ezeket a csúcsokat összekötő út minimális hosszát. $u$ $v$

A gráf bármely maximálisan összefüggő részgráfját a gráf összekapcsolt komponensének (vagy egyszerűen komponensének) nevezzük . A „maximum” szó a befogadás tekintetében maximumot jelent, vagyis nem szerepel egy összefüggő részgráfban nagyszámú elemmel. $G$ $G$

Egy gráf élét hídnak nevezzük, ha eltávolítása megnöveli az összetevők számát.

A grafikonok további jellemzői

A grafikon neve:

össze van kötve ,ha bármely csúcshozvan egy elérési út innen:-ig. $u$ $v$ $u$ $v$
erősen vagy irányítottan kapcsolódik , ha orientált, és van egy orientált út bármely csúcsból bármely másikba.
egy fa , ha össze van kötve és nem tartalmaz nem triviális ciklusokat.
teljes , ha a két (különböző, ha a hurkok nem megengedettek) csúcsai közül bármelyiket él köti össze.
kétrészes , ha csúcsai feloszthatók két nem metsző részhalmazra, ésúgy, hogy bármely él összeköt egy -ból származócsúcsot egy -ból származó csúcsgal. $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$
k-partiális , ha csúcsai nem metsző részhalmazokra , , … részhalmazokra oszthatók úgy, hogy nincsenek élek, amelyek ugyanazon részhalmaz csúcsait kötnék össze. $k$ $V_{1}$ $V_{2}$ $V_{k}$
teljes kétrészes , ha egy részhalmaz minden csúcsa egy éllel össze van kötve egy másik részhalmaz minden csúcsával.
sík , ha a gráf diagrammal ábrázolható síkon élek keresztezése nélkül.
súlyozott , ha a gráf minden éléhez hozzá van rendelve egy bizonyos szám, amelyet az él súlyának nevezünk.
akkordális , ha a gráf nem tartalmaz háromnál hosszabb indukált ciklusokat.

Ez is előfordul:

A gráf fogalmának általánosítása

Az egyszerű gráf egy egydimenziós egyszerű komplex .

Elvontabban a gráf hármasként definiálható , ahol és néhány halmaz ( csúcsokból és élekből ), és egy beesési függvény (vagy incidens ), amely minden élhez (rendezett vagy rendezetlen) egy pár csúcsot és -tól ( végei ). Ennek a koncepciónak a különleges esetei a következők: $(V,E,\varphi )$ $V$ $E$ $\varphi$ $e\in E$ $u$ $v$ $V$

Euler-gráfok - olyan gráf, amelyben van egy ciklikus Euler-út ( Euler-ciklus );

A gráf ábrázolásának módjai a számítástechnikában

Szomszédsági mátrix

Egy táblázat, ahol az oszlopok és a sorok is megfelelnek a gráf csúcsainak. Ennek a mátrixnak minden cellájába egy szám van írva, amely meghatározza a kapcsolat jelenlétét a felső sorból a felső oszlopba (vagy fordítva).

Ez a legkényelmesebb módja a sűrű grafikonok ábrázolásának.

Hátránya a memóriaigény, amely egyenesen arányos a csúcsok számának négyzetével.

Kétdimenziós tömb;
Mátrix hézagokkal;
Implicit beállítás (függvény használatával).

Előfordulási mátrix

Egy táblázat, ahol a sorok a gráf csúcsainak, az oszlopok pedig a grafikon hivatkozásainak (éleinek) felelnek meg. Egy mátrixcellában egy sor és egy oszlop metszéspontjában a következőt írjuk: $én$ $j$

egy ha a kapcsolat "elhagyja" a tetejét ,

j

én

-1, ha a kapcsolat "belép" a csúcsba, 0 minden más esetben (vagyis ha a kapcsolat hurok, vagy a kapcsolat nem incidens a csúcsban)

Ez a módszer meglehetősen nagy kapacitású (a méret arányos ) a tároláshoz, ezért nagyon ritkán, speciális esetekben alkalmazzák (például ciklusok gyors megtalálásához egy grafikonon). $|V||E|$

Szomszédsági lista

Egy lista, ahol a gráf minden csúcsa egy karakterláncnak felel meg, amely a szomszédos csúcsok listáját tárolja. Az ilyen adatstruktúra nem a szokásos értelemben vett táblázat, hanem egy "listák listája".

Memória mérete: . $O(|V|+|E|)$

Ez a legkényelmesebb módja a ritka gráfok ábrázolásának, valamint az alapvető gráf bejárási algoritmusok szélességben vagy mélységben történő megvalósításánál, ahol gyorsan meg kell szerezni az éppen nézett csúcs "szomszédjait".

Élek listája

Egy lista, ahol a gráf minden éle egy karakterláncnak felel meg, amely az élre eső két csúcsot tárolja.

Memória mérete: . $O(|E|)$

Ez a legkompaktabb módja a grafikonok ábrázolásának, ezért gyakran használják külső tárolásra vagy adatcserére.

Leíró nyelvek és grafikus programok

Leírás nyelvei

A gépi feldolgozásra alkalmas és egyben az emberi érzékelés számára kényelmes grafikonok leírására több szabványos nyelvet használnak, beleértve:

PONT
GraphML
Triviális grafikon formátum
GML
GXL
XGMML
DGML

Programok építése

Egy sor kereskedelmi programot fejlesztettek ki gráfok készítésére, például a gráfépítés az ILOG alkalmazási szoftvercsomagok alapja (2009 óta az IBM Corporation tulajdona ), többek között a GoView, Lassalle AddFlow, LEDA (van ingyenes kiadás) ).

Van még egy ingyenes grafikus program, az igraph és egy ingyenes könyvtár , a Boost .

Vizualizációs programok

A következő szoftvereszközöket használják a grafikonok megjelenítéséhez :

Graphviz ( Eclipse Public License )
LION Graph Visualizer.
A grafikonelemző egy orosz nyelvű program, egyszerű felhasználói felülettel ( GNU LGPL ; csak Windows).
A Gephi egy grafikus keretrendszer gráfok ábrázolására és tanulmányozására ( GNU GPL , CDDL ).
A GraphX-könyvtár egy ingyenes .NET -könyvtár grafikonok kiszámításához és rajzolásához, WPF 4.0 használatával .
Az MSAGL könyvtár a .NET ingyenes könyvtára [3] .

Lásd még

Jegyzetek

↑ Burkatovskaya, 2014 , p. 3.
↑ 1 2 3 Burkatovskaya, 2014 , p. 6.
↑ Microsoft Automatic Graph Layout – Microsoft Research . research.microsoft.com. Letöltve: 2015. november 15. Az eredetiből archiválva : 2012. május 14. (határozatlan)

Irodalom

Burkatovskaya Yu. B. A gráfok elmélete. - Tomszk: Tomszki Politechnikai Egyetem Kiadója, 2014. - T. 1. - 200 p.
Distel R. Gráfelmélet. - Novoszibirszk: A Matematikai Intézet kiadója. S. L. Sobolev SO RAN, 2002. - 336 p. - ISBN 5-86134-101-X.
Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Előadások a gráfelméletről. M.: Nauka, 1990. 384 p. (Ed. 2, rev. M.: URSS, 2009. 392 p.)
Kasyanov V.N., Evstigneev V.A. Grafikonok a programozásban: feldolgozás, megjelenítés és alkalmazás. - Szentpétervár. : BHV-Petersburg, 2003. - S. 1104. - ISBN 5-94157-184-4 .
Kirsanov M.N. Grafikonok juharban. — M. : Fizmatlit, 2007. — 168 p. - ISBN 978-5-9221-0745-7 .
Kormen T. M. és társai VI. rész. Algoritmusok gráfokkal // Algoritmusok: szerkesztés és elemzés = Introduction to Algorithms. - 2. kiadás - M. : Williams, 2006. - S. 1296. - ISBN 0-07-013151-1 .
Ore O. Gráfelmélet. — M .: Nauka, 1968. — 336 p.
Grafikonok // Egy fiatal matematikus enciklopédikus szótára / Összeáll. A. P. Savin. - M . : Pedagógia , 1985. - S. 86 -88. — 352 p.
Salii VN, Bogomolov AM A diszkrét rendszerek elméletének algebrai alapjai. - M .: Fizikai és matematikai irodalom, 1997. - ISBN 5-02-015033-9 .
Wilson R. Bevezetés a gráfelméletbe. — M .: Mir, 1977. — 208 p.
Harari F. Gráfelmélet. - M .: Mir, 1973.