Kaavio (matematiikka)

Graafi on matemaattinen abstraktio minkä tahansa luonteisesta todellisesta järjestelmästä, jonka kohteilla on pareittainen yhteys. Graafi matemaattisena objektina on kokoelma kahdesta joukosta - itse objektien joukosta, jota kutsutaan kärkijoukoksi , ja niiden parittaisten yhteyksien joukosta, jota kutsutaan reunajoukoksi. Reunajoukon elementti on kärkijoukon alkioiden pari.

Graafeja käytetään laajasti nykyaikaisessa tieteessä ja tekniikassa. Niitä käytetään sekä luonnontieteissä (fysiikka ja kemia) että yhteiskuntatieteissä (esim. sosiologia), mutta graafien käyttö on saanut suurimman mittakaavan tietojenkäsittelytieteessä ja verkkoteknologioissa.

Yksinkertaisina esimerkkinä elämästä voidaan antaa tietyn lentoyhtiön lentokaavio, joka on mallinnettu graafilla, jossa graafin kärjet ovat kaupungit ja reunat kaupunkipareja yhdistäviä lentoja. Tietokoneen hakemistopuu on myös graafi: asemat, kansiot ja tiedostot ovat huippuja, ja reunat osoittavat tiedostojen ja kansioiden sisäkkäisyyden kansioissa ja asemissa [1] . Wikipedian rakennetta mallintaa suunnattu graafi , jossa artikkelit ovat graafin kärkipisteitä ja hyperlinkit kaaria ( temaattinen kartta ).

Graafit ovat graafiteorian pääasiallinen tutkimuskohde .

Määritelmät

Graafeilla mallinnetut todellisen luonnon järjestelmät ovat hyvin erilaisia, joten graafisia tyyppejä on erilaisia. Yksinkertaisin abstraktio järjestelmistä, joissa on pareittain kytkettyjä elementtejä, on yksinkertainen graafi .

Yksinkertainen kaavio

Määritelmä. Yksinkertainen graafi on kahden joukon kokoelma - ei-tyhjä joukko ja joukko joukon eri elementtien järjestämättömiä pareja . Joukkoa kutsutaan kärkijoukoksi , joukkoa kutsutaan reunajoukoksi $G(V,E)$ $V$ $E$ $V$ $V$ $E$

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

eli joukko koostuu joukon 2-alkioisista osajoukoista . $E$ $V$

Aiheeseen liittyvät termit

Graafiteorialla ei ole vakiintunutta terminologiaa. Tästä syystä joissakin julkaisuissa voidaan käyttää muita kuin alla lueteltuja termejä.

Graafin kärki (solmu, piste) ( eng. vertex, node, point ) on kärkijoukon elementti ; $G$ $v\in V(G)$

Graafin reuna (viiva) ( englanniksi edge, line ) on reunajoukon elementti , tai , jossa ; $G$ $e\in E(G)$ $e=\left\{v_{1},v_{2}\right\}$ $v_{1}\in V(G),\quad v_{2}\in V(G)$

Graafin elementit ovat sen kärjet ja graafin reunat ; $G$ $v\in V(G)$ $e\in E(G)$

Graafin järjestys ( englanniksi järjestys ) on kärkijoukon kardinaaliluku tai toisin sanoen pisteiden lukumäärä; $G$ $n=|V(G)|$

Graafin koko ( englanniksi koko ) on reunajoukon kardinaaliluku tai toisin sanoen reunojen lukumäärä; $G$ $m=|E(G)|$

Vertex on sattuma reunaan , jos ; _ sitten he myös sanovat, että kohdassa on reuna ; $v$ $e$ $v\in e$ $e$ $v$

Loppupisteet (päät) ( eng. endvertices, ends ) ovat kaksi kärkeä, jotka osuvat reunaan. Reuna yhdistää ( englanniksi joins ) päätypisteensä;

Naapuri (naapuri) kärkipisteet ( englanniksi naapurit, vierekkäiset ) ovat sellaisia pisteitä ja että tai toisin sanoen molemmat kärjet ovat päätepisteitä yhdelle reunalle; $v_{1}$ $v_{2}$ $\left\{v_{1},v_{2}\right\}\in E(G)$

Vierekkäiset reunat ( englanniksi vierekkäiset reunat ) ovat reunoja, jotka osuvat yhteen kärkeen tai - vierekkäin; ${\displaystyle e_{1}=\left\{v,v_{1}\oikea\))$ $e_{2}=\left\{v,v_{2}\right\}$

Huippupisteen aste (valenssi) ( eng. kraadi, valenssi ) on siihen osuvien reunojen lukumäärä. Vertexin aste merkitään ; $d(v)$

Eristetty kärki ( eng. isolated ) on kärki, jolla on aste , eli se ei ole minkään reunan loppu; $d(v)=0$

Riippuva kärki (lehti) ( eng. leaf ) on kärki, jolla on aste , eli joka on tasan yhden reunan loppu. $d(v) = 1$

Tyypillisesti graafi kuvataan kaaviona : kärjet - pisteet, reunat - viivat.

Pseudografi

Pseudografi on kahden joukon kokoelma - ei-tyhjä joukko ja joukko joukon järjestämättömiä elementtipareja . $G(V,E)$ $V$ $E$ $V$

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

Elementti on sallittu pseudografin reunojen joukossa . $\left\{v,v\right\}\in E(G)$

Silmukka on elementti , joka on reuna, jonka päätypisteet ovat samat. $e=\left\{v,v\right\}$

Toisin sanoen, jos joukon E alkiot voivat olla silmukoita, niin graafia kutsutaan pseudografiksi [2] .

Multigraph

Multigrafi on kahden joukon kokoelma - ei-tyhjä joukko ja joukko joukon eri elementtien järjestämättömiä pareja . $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

Useat reunat ovat identtisiä multisetin elementtejä, eli reunoja, joiden päätypisteet osuvat yhteen. $\left\{e,e,\dots ,e\right\}\in \mathbf {E}$

Toisin sanoen, jos ei joukkoa, vaan perhettä, eli jos se sisältää samat alkiot, niin tällaisia elementtejä kutsutaan useiksi reunuksiksi ja graafia kutsutaan multigrafiksi [2] . $E$ $\mathbf {E}$

Pseudomultigrafi

Pseudomultigrafi on kokoelma kahdesta joukosta - ei-tyhjästä joukosta ja joukon järjestämättömien elementtiparien monijoukosta . $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

Toisin sanoen, jos perhe, joka sisältää samat elementit (useita särmiä) ja voi sisältää silmukoita, graafia kutsutaan pseudomultigrafiksi [2] . $\mathbf {E}$ $\mathbf {E}$

Suunnattu graafi

Suunnattu graafi (digrafi) ( eng. suuntautunut graafi tai dirgaph ) on kahden joukon joukko - ei-tyhjä joukko ja joukko kaaria tai järjestettyjä pareja joukon eri elementeistä $G(V,E)$ $V$ $E$ $V$

G(V,E)=\left\langle V,E\oikea\rangle ,\quad V\neq \varnothing ,\quad \left\langle \left\{v_{1},v_{2}\ oikea\},\pre \oikea\kulma \in E,\quad v\in V

yhdessä kahden näytön kanssa

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

missä kuvaus määrittää kullekin kaarelle sen alkupisteen (kaaren alun) ja kuvaus määrittää kullekin kaarelle sen loppupisteen (kaaren loppu) . Sanotaan, että kaari johtaa paikasta toiseen $init:E\rightarrow V$ $init(e)$ $ter:E\rightarrow V$ $ter(e)$ $e$ $init(e)$ $ter(e)$

Sekakaavio

Sekoitettu graafi on kolmen joukon kokoelma - ei-tyhjä pistejoukko ja joukko kaaria tai järjestettyjä pareja joukon eri elementeistä ja joukko joukon eri elementtien järjestämättömien parien reunoja. $G(V,E,U)$ $V$ $E$ $V$ $U$ $V$

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

yhdessä kahden näytön kanssa

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

Suunnatut ja suuntaamattomat graafit ovat sekagraafien erikoistapauksia.

Isomorfiset kaaviot

Graafia kutsutaan graafin isomorfiseksi, jos graafin kärkijoukosta on bijektio graafin kärkijoukkoon , jolla on seuraava ominaisuus: jos graafilla on reuna kärjestä kärkeen , niin graafi täytyy olla reuna kärjestä kärkeen ja päinvastoin - jos graafilla on reuna kärjestä kärkeen , niin graafilla on oltava reuna kärjestä kärkeen . Suunnatun graafin tapauksessa tämän bijektion on myös säilytettävä reunan suunta. Painotetun graafin tapauksessa bijektion on myös säilytettävä reunan paino. $G$ $H$ $f$ $G$ $H$ $G$ $A$ $B$ $H$ $fa)$ $f(B)$ $H$ $A$ $B$ $G$ $f^{-1}(A)$ $f^{-1}(B)$

Muut asiaan liittyvät määritelmät

Graafin reitti on äärellinen kärkijono, jossa jokainen kärki (paitsi viimeinen) on yhdistetty sekvenssin seuraavaan kärkeen reunalla. Ketju on reitti ilman toistuvia reunoja. Yksinkertainen polku on polku ilman toistuvia pisteitä (mikä tarkoittaa, että yksinkertaisessa polussa ei ole toistuvia reunoja).

Suuntareitti (tai polku ) digrafissa on äärellinen kärkien ja kaarien sarja, jossa jokainen elementti liittyy edelliseen ja seuraavaan.

Jakso on ketju, jonka ensimmäinen ja viimeinen kärki kohtaavat. Tässä tapauksessa polun (tai syklin) pituus on sen muodostavien reunojen lukumäärä . Huomaa, että jos kärjet ja ovat jonkin reunan päät, niin tämän määritelmän mukaan sarja on sykli. Tällaisten "rappeutuneiden" tapausten välttämiseksi otetaan käyttöön seuraavat käsitteet. $u$ $v$ $(u, v, u)$

Polkua (tai sykliä) kutsutaan yksinkertaiseksi , jos sen reunat eivät toistu; alkeis , jos se on yksinkertainen ja sen kärjet eivät toistu (poikkeuksena alku- ja loppulause syklin tapauksessa).

Polkujen ja syklien yksinkertaisimmat ominaisuudet:

jokainen polku, joka yhdistää kaksi kärkeä, sisältää peruspolun, joka yhdistää samat kaksi kärkeä;
jokainen yksinkertainen ei-alkeispolku sisältää alkeissyklin ;
jokainen yksinkertainen sykli, joka kulkee jonkin kärjen (tai reunan) kautta, sisältää saman kärjen (tai reunan) läpi kulkevan alkeis- (ali)syklin;
silmukka on perussykli.

Graafin kärkijoukon binäärirelaatio , joka annetaan muodossa "on polku kohteesta kohteeseen ", on ekvivalenssirelaatio , ja siksi se jakaa tämän joukon ekvivalenssiluokkiin, joita kutsutaan graafin yhdistetyiksi komponenteiksi . Jos kaaviossa on täsmälleen yksi yhdistetty komponentti, graafi on yhdistetty. Yhdistetylle komponentille voidaan ottaa käyttöön pisteiden välisen etäisyyden käsite nämä kärjet yhdistävän polun minimipituutena. $u$ $v$

Mitä tahansa graafin maksimaalista yhdistettyä osagraafia kutsutaan graafin yhdistetyksi komponentiksi (tai yksinkertaisesti komponentiksi) . Sana "maksimi" tarkoittaa enimmäismäärää sisällyttämisen suhteen, eli se ei sisälly yhdistettyyn osagraafiin, jossa on suuri määrä elementtejä. $G$ $G$

Graafin reunaa kutsutaan sillaksi, jos sen poistaminen lisää komponenttien määrää.

Kuvaajien lisäominaisuudet

Kaaviota kutsutaan:

kytketty ,jos jollekin pisteelleon polku osoitteestakohteeseen. $u$ $v$ $u$ $v$
vahvasti yhdistetty tai suunnattu , jos se on suunnattu ja mistä tahansa kärjestä toiseen on suunnattu polku.
puu, jos se on yhdistetty eikä sisällä ei-triviaaleja syklejä.
täydellinen , jos jokin sen kahdesta (eri, jos silmukat eivät ole sallittuja) kärjestä on yhdistetty reunalla.
kaksiosainen , jos sen kärjet voidaan jakaa kahteen ei-leikkaavaan osajoukkoonjaniin, että mikä tahansa reuna yhdistääkärjen kohteesta. $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$
k-osittais , jos sen kärjet voidaan jakaa ei-leikkaaviin osajoukkoon , , …, jolloin ei ole reunoja, jotka yhdistävät saman osajoukon kärkipisteitä. $k$ $V_{1}$ $V_{2}$ $V_{k}$
täydellinen bipartite , jos yhden osajoukon jokainen kärki on yhdistetty reunalla toisen osajoukon jokaiseen kärkeen.
taso , jos graafi voidaan esittää kaaviolla tasossa ilman reunoja risteäviä.
painotettu , jos jokaiselle graafin reunalle on määritetty tietty numero, jota kutsutaan reunan painoksi.
sointu , jos kuvaaja ei sisällä indusoituja jaksoja, joiden pituus on suurempi kuin kolme.

Tapahtuu myös:

Graafin käsitteen yleistäminen

Yksinkertainen graafi on yksiulotteinen yksinkertainen kompleksi .

Abstraktimmin graafi voidaan määritellä kolmiosaksi , jossa ja ovat joitain joukkoja ( vastaavasti kärkejä ja reunoja ), ja se on insidenssifunktio (tai insidentor ), joka määrittää kullekin reunalle (järjestetylle tai järjestämättömälle) parin pisteitä ja alkaen (sen päät ). Tämän konseptin erityistapaukset ovat: $(V,E,\varphi )$ $V$ $E$ $\varphi$ $e\in E$ $u$ $v$ $V$

Eulerin graafit - graafi, jossa on syklinen Eulerin polku ( Eulerin sykli );

Kuvaajan esittämistapoja tietojenkäsittelytieteessä

Vierekkäisyysmatriisi

Taulukko, jossa sekä sarakkeet että rivit vastaavat graafin huippuja. Tämän matriisin jokaiseen soluun kirjoitetaan numero, joka määrittää yhteyden olemassaolon yläriviltä ylimpään sarakkeeseen (tai päinvastoin).

Tämä on kätevin tapa esittää tiheitä kaavioita.

Haittapuolena ovat muistivaatimukset, jotka ovat suoraan verrannollisia pisteiden lukumäärän neliöön.

Kaksiulotteinen matriisi;
Matriisi, jossa on aukkoja;
Implisiittinen asetus (funktion avulla).

Ilmaantuvuusmatriisi

Taulukko, jossa rivit vastaavat graafin kärkipisteitä ja sarakkeet vastaavat kaavion linkkejä (reunoja). Matriisisoluun rivin ja sarakkeen leikkauskohdassa kirjoitetaan seuraava: $i$ $j$

yksi jos yhteys "poistuu" ylhäältä ,

j

i

-1, jos yhteys "tulee" kärkeen, 0 kaikissa muissa tapauksissa (eli jos yhteys on silmukka tai yhteys ei ole sattumanvarainen kärjessä)

Tämä menetelmä on melko tilava (koko on verrannollinen ) tallennusta varten, joten sitä käytetään erittäin harvoin, erikoistapauksissa (esimerkiksi syklien nopeaan löytämiseen kaaviosta). $|V||E|$

Naapuriluettelo

Luettelo, jossa jokainen graafin kärkipiste vastaa merkkijonoa, joka tallentaa luettelon vierekkäisistä pisteistä. Tällainen tietorakenne ei ole taulukko tavallisessa merkityksessä, vaan se on "luetteloluettelo".

Muistin koko :. $O(|V|+|E|)$

Tämä on kätevin tapa esittää harvat graafit, samoin kuin toteutettaessa perusgraafin läpikulkualgoritmeja leveydellä tai syvyydellä, jolloin sinun on nopeasti löydettävä parhaillaan tarkasteltavan huippupisteen "naapurit".

Lista reunoista

Luettelo, jossa jokainen graafin reuna vastaa merkkijonoa, joka tallentaa kaksi reunaan sattuvaa kärkeä.

Muistin koko :. $O(|E|)$

Tämä on kompaktin tapa esittää kuvaajia, joten sitä käytetään usein ulkoiseen tallennustilaan tai tiedonvaihtoon.

Kuvauskielet ja graafiset ohjelmat

Kuvauskielet

Konekäsittelyyn soveltuvien ja samalla ihmisen havainnointiin sopivien kuvaajien kuvaamiseen käytetään useita standardoituja kieliä, mukaan lukien:

PISTE
GraphML
Triviaali kaaviomuoto
GML
GXL
XGMML
DGML

Rakennusohjelmia

Kuvaajien rakentamiseen on kehitetty sarja kaupallisia ohjelmia, esimerkiksi graafin rakentaminen on perusta ILOG -sovellusohjelmistopaketeille (vuodesta 2009 IBM Corporationin omistama ), muiden ohjelmien lisäksi - GoView, Lassalle AddFlow, LEDA (ilmainen versio on olemassa). ).

Saatavilla on myös ilmainen graafinen ohjelma igraph ja ilmainen kirjasto nimeltä Boost .

Visualisointiohjelmat

Seuraavia ohjelmistotyökaluja käytetään kaavioiden visualisointiin :

Graphviz ( Eclipse Public License )
LION Graph Visualizer.
Graafianalysaattori on venäjänkielinen ohjelma, jossa on yksinkertainen käyttöliittymä ( GNU LGPL ; vain Windows).
Gephi on graafinen kehys graafien esittämiseen ja tutkimiseen ( GNU GPL , CDDL ).
GraphX -kirjasto on ilmainen .NET -kirjasto kaavioiden laskemiseen ja piirtämiseen WPF 4.0 :lla .
MSAGL-kirjasto on ilmainen .NET-kirjasto [3] .

Katso myös

Muistiinpanot

↑ Burkatovskaya, 2014 , s. 3.
↑ 1 2 3 Burkatovskaya, 2014 , s. 6.
↑ Microsoft Automatic Graph Layout - Microsoft Research . research.microsoft.com. Haettu 15. marraskuuta 2015. Arkistoitu alkuperäisestä 14. toukokuuta 2012. (määrätön)

Kirjallisuus

Burkatovskaya Yu. B. Graafien teoria. - Tomsk: Tomskin ammattikorkeakoulun kustantamo, 2014. - T. 1. - 200 s.
Distel R. Graafiteoria. - Novosibirsk: Matematiikan instituutin kustantamo. 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. Graafiteorian luentoja. M.: Nauka, 1990. 384 s. (Toim. 2, rev. M.: URSS, 2009. 392 s.)
Kasjanov V.N., Evstigneev V.A. Graafit ohjelmoinnissa: käsittely, visualisointi ja sovellus. - Pietari. : BHV-Petersburg, 2003. - S. 1104. - ISBN 5-94157-184-4 .
Kirsanov M.N. Kaaviot vaahterassa. — M .: Fizmatlit, 2007. — 168 s. - ISBN 978-5-9221-0745-7 .
Kormen T. M. et ai., osa VI. Algoritmit graafien kanssa työskentelyyn // Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. - 2. painos - M. : Williams, 2006. - S. 1296. - ISBN 0-07-013151-1 .
Ore O. Graafiteoria. - M .: Nauka, 1968. - 336 s.
Kaaviot // Nuoren matemaatikon tietosanakirja / Comp. A.P. Savin. - M . : Pedagogiikka , 1985. - S. 86 -88. — 352 s.
Salii VN, Bogomolov AM Diskreettien järjestelmien teorian algebralliset perusteet. - M .: Fysikaalinen ja matemaattinen kirjallisuus, 1997. - ISBN 5-02-015033-9 .
Wilson R. Johdatus graafiteoriaan. - M .: Mir, 1977. - 208 s.
Harari F. Graafiteoria. - M .: Mir, 1973.