Graafiteoriassa graafi on abstrakti rakenne, joka edustaa objektijoukkoa yhdessä näiden objektien välisten yhteyksien kanssa. Objektien matemaattisia abstraktioita kutsutaan graafin solmuiksi (tai kulmiksi ). Solmujen välisiä parittaisia ​​yhteyksiä kutsutaan reunoiksi (joskus myös kaariksi ). Reunat voivat olla suunnattuja tai suuntaamattomia . Kaaviot piirretään usein graafisesti esittämällä solmut pisteillä ja reunat viivoilla. ^[1]

Sukupuun kaavamainen rakenne

Wienin metron suunnitelma

Kuvaavia esimerkkejä kaavioista ovat sukupuu tai kaupungin metroverkko (katso kuvat). Sukupuussa jokainen solmu edustaa perheenjäsentä ja jokainen reuna on yhteys vanhemman ja lapsen välillä. Metroverkossa jokainen solmu edustaa metroasemaa ja jokainen reuna edustaa suoraa junayhteyttä kahden aseman välillä.

kaavioiden tyypit

Suuntaamaton kaavio

Suuntaamattomissa graafisissa solmujen väliset yhteydet on merkitty reunoilla . Reunoilla ei ole suuntaa. Kukin reuna voidaan ajaa molempiin suuntiin.

Suunnattu kaavio (digraafi)

Digrafeissa reunat merkitään nuolilla viivojen sijaan , ja nuoli osoittaa niiden alusta niiden päätesolmuun. Tämä tekee selväksi, että graafin jokainen reuna voidaan kulkea vain yhteen suuntaan. ^[2]

puu

Graafiteoriassa puu on erityinen graafi, joka on yhdistetty eikä sisällä suljettuja polkuja , eli syklejä , joiden pituus on suurempi tai yhtä suuri kuin 3. Kaikilla puilla kärkien lukumäärä on selvästi 1 suurempi kuin reunojen lukumäärä.

Puilla on monia käytännön käyttötarkoituksia, varsinkin tietojenkäsittelytieteessä . Monet algoritmit ohjelmoidaan puiden avulla . Esimerkiksi verkot , liikenneverkot tai sähköverkot voidaan kulkea tehokkaasti leveys- tai syvyyshakulla . Tekoäly- ja strategiapelien alalla alfabeta-haku on tärkeä. Se perustuu hakupuihin .

monikuvaaja

Multigrafi: Useat reunat visualisoidaan painotetulla reunalla

Ns. multigrafeissa kaksi solmua voidaan yhdistää myös useilla reunoilla ^[3] , mikä ei ole sallittua yksinkertaisissa graafisissa graafisissa muodoissa . Lisäksi multigrafit saavat sisältää silmukoita: reunoja, jotka johtavat samaan kärkeen, josta ne ovat peräisin. ^[1]

Jos solmuja yhdistää useita reunoja ^[3] , piirretään usein vain yksi reuna ja näiden kahden solmun välinen reunojen lukumäärä kirjoitetaan yhden reunan reunapainoksi. Esimerkissä solmujen A ja D välillä on 60 reunaa . Sen sijaan, että piirrettäisiin kaikki 60 reunaa, piirretään reuna, jonka reunapaino on 60.

tasokaavio

Tasograafi on graafi , joka voidaan piirtää tasolle ja jossa on pisteet solmuille ja viivat reunoille siten, että mikään reuna ei leikkaa. Jokaisella tasograafilla on kaksoisgraafi . Tämä on kaavio, jossa kaavion jokainen pinta liittyy solmuun , joka sijaitsee kyseisen pinnan sisällä, ja päinvastoin. Tasograafien duaalisuus on aina molemminpuolinen, eli minkä tahansa tasograafin duaaligraafin duaaligraafi on alkuperäinen tasograafi.

Eulerin monitahoteoreema pätee tasokaavioihin, jotka usein esitetään yhtälöllä ${\displaystyle E-K+F=2}$

hypergrafia

Hypergrafeissa reuna (kutsutaan myös hyperedgeksi ) ei yhdistä vain kahta, vaan useita solmuja samanaikaisesti. Esimerkiksi hypergraafit voidaan esittää useilla tasokaavioilla , joissa on reunaindeksointi . Vähäreunaiset hypergraafit (ns. harvat graafit ) piirretään piirtämällä joukko pisteitä, jotka vastaavat huippuja, ja sitten hyperreunaan kuuluvat pisteet ympäröidään suljetulla viivalla, joka on siten osajoukko .siihen kuuluvista solmuista kaikissa solmuissa. Hypergrafeissa, joissa on useita reunoja, tämä esitys tulee kuitenkin nopeasti hämmentäväksi. On vähemmän intuitiivista, mutta selvempää esittää hypergrafia kaksiosaisena metagraafina, jossa toinen kahdesta kaksiosaisesta joukosta vastaa hypergraafin solmuja ja toinen kaksiosaisuus on asetettu hypergraafin hyperreunoihin. Näiden kahden bipartitiojoukon väliset reunat symboloivat sitten solmujen liittymistä hyperreunoihin.

Stephen Wolframin fysiikkaprojekti (katso myös: Wolfram Research and Mathematica ) fysiikan perusteiden selittämiseksi perustuu muun muassa hypergraafien sääntöavaruuteen: "Ja ainakin tietyllä likiarvolla voimme sitten sanoa, että energia liittyy aktiivisuuteen hypergrafissa, joka levittää tietoa ajan kuluessa, kun taas liikemäärä liittyy toimintaan, joka levittää tietoa avaruudessa." ^[4]

määritelmät

Graafi on järjestetty pari , joka tarkoittaa joukkoa solmuja ( kärkipisteitä , joskus kutsutaan myös kulmiksi ) ja joukkoa reunoja ( reuna /reunat , joskus kutsutaan myös kaariksi ). missä on ${\displaystyle G}$ ${\näyttötyyli (V,E)}$${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle E}$

• suuntaamattomat graafit ilman useita reunoja kaikkien 2-elementtisten osajoukkojen [ ^1] osajoukko ,${\displaystyle V}$
• suunnatut graafit ilman useita reunoja kaikkien parien (i, j) osajoukko, joka saadaan karteesisesta tulosta , ^[5]${\displaystyle V\times V}$
• suuntaamattomat graafit, joissa on yhdistetty useita reunoja, monijoukko kaikkien 2-elementtisten osajoukkojen joukossa , eli funktio ,${\displaystyle W}$${\displaystyle V}$ ${\displaystyle E\colon W\to \mathbb {N} _{0}}$
• suunnatut graafit , joissa on yhdistetty useita reunoja multiset yli karteesisen tuotteen , eli funktio${\displaystyle V\times V}$${\displaystyle E\colon V\times V\to \mathbb {N} _{0}}$
• suunnatut graafit, joissa on itsessään useita reunoja , joiden elementtejä pidetään reunoina kahden funktion avulla, jotka antavat elementeille lähde- ja kohdepisteen (sellainen graafi on sama kuin funktori , jossa melko hallittava kategoria kahdella esineitä ja kaksi erinomaista nuolta)${\displaystyle \mathrm {src} ,\mathrm {tgt} \colon E\to V}$ ${\displaystyle G\colon {\mathcal {G}}\to \mathbf {Set} }$${\displaystyle {\mathcal {G}}}$${\displaystyle {\mathcal {G}}=\{V{\stackrel {\mathrm {src} }{\longleftarrow }}E{\stackrel {\mathrm {tgt} }{\longrightarrow }}V\}}$
• Hypergraafit ovat osajoukko potenssijoukosta . ^[1]${\displaystyle V}$

Suuntaamaton graafi ilman useita reunoja

Suunnattu graafi ilman useita reunoja

Suuntaamaton graafi, jossa on useita reunoja

Suunnattu graafi, jossa on useita reunoja

Lisäys "ilman useita reunoja" jätetään yleensä pois ja kaavioita, joissa on useita reunoja, kutsutaan multigrafeiksi . Lisäksi attribuutti "ohjaamaton" jätetään yleensä pois ja vain suunnatut graafit merkitään eksplisiittisesti. Suuntaamattomia kuvaajia, joissa ei ole useita reunoja, kutsutaan usein myös tavallisiksi tai yksinkertaisiksi . Suunnattujen graafien toinen nimi on digraph (suunnattu graafi).

Johdetut termit

Sen sijaan , että tunnistaisit graafin kärkijoukot ja reunat symboleilla ja , voidaan myös määritellä yleisiä karttoja , jotka kuvaavat graafin sen kärkijoukkoon tai reunaan. Kahdelle kaaviolle ja merkitse ja sekä ja . ${\displaystyle G}$${\displaystyle V}$${\displaystyle E}$ ${\displaystyle V}$${\displaystyle E}$${\displaystyle G_{1}=(V_{1},E_{1})}$${\displaystyle G_{2}=(V_{2},E_{2})}$${\displaystyle V(G_{1}):=V_{1}}$${\displaystyle E(G_{1}):=E_{1}}$${\displaystyle V(G_{2})=V_{2}}$${\displaystyle E(G_{2})=E_{2}}$

Epäselvyys ja hyväksytään tällä merkinnällä, vaikka kuvaukset edustavat jotain muuta kuin niihin liittyvää solmu- ja reunajoukkoa. Käytännössä on suositeltavaa merkitä solmujen tai reunojen joukko argumentin kanssa tai ilman , tai määritetyt kuvaukset argumentilla. ${\displaystyle V(G)=V}$${\displaystyle E(G)=E}$${\displaystyle V}$${\displaystyle E}$${\displaystyle V}$${\displaystyle E}$

Jos on graafi, niin sanotaan yleensä olevan solmu tai kärki , jos kuuluu . Reunat merkitään myös nimellä ${\displaystyle G}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$${\displaystyle V(G)}$${\displaystyle e\in E(G)}$

• if :n suuntaamaton reuna on suuntaamaton graafi.${\displaystyle G}$${\displaystyle G}$
• if :n suunnattu reuna on suunnattu graafi.${\displaystyle G}$${\displaystyle G}$
• If :n hyperedge on hypergraafi.${\displaystyle G}$${\displaystyle G}$

Suuntaamattomassa reunassa merkitsemme ja -kohdan loppusolmuina . Suunnatussa reunassa kutsumme aloitussolmua ja loppusolmua . _ _${\displaystyle e=\lbrace v,w\rbrace }$${\displaystyle v}$${\displaystyle w}$${\displaystyle e}$${\displaystyle e=(v,w)}$${\displaystyle v}$${\displaystyle w}$${\displaystyle e}$

Multigraphs tarkoittaa moninkertaisuutta . _ Tarvittaessa puhutaan moni- tai monireunasta . ${\displaystyle E(G)(e)}$${\displaystyle e}$${\displaystyle E(G)(e)>1}$

Jos suunnattujen graafien reunalla on muoto , sitä kutsutaan silmukaksi . Jos monigraafin silmukka on myös monireuna , sitä kutsutaan monisilmukaksi . Suunnattuja kaavioita ilman silmukoita kutsutaan silmukattomiksi tai silmukattomiksi . ${\displaystyle e}$${\displaystyle (v,v)}$${\displaystyle e}$${\displaystyle G}$

Graafin solmujen lukumäärä on sen solmujen lukumäärä ja reunojen määrä sen reunojen lukumäärä (multigrafeissa yksi summautuu reunojen moninaisuuteen). ${\displaystyle n(G)=\vert V(G)\vert }$${\displaystyle G}$ ${\displaystyle m(G)=\vert E(G)\vert }$

Kahta solmua kutsutaan vierekkäisiksi , jos reuna yhdistää ne.

erikoistapaukset

Jos reuna yhdistää kaksi solmua suunnatussa graafissa ja reuna yhdistää samat solmut vastakkaiseen suuntaan, voidaan myös pitää molempia yhdessä suuntaamattomana reunana suunnatussa graafissa. Jos särmiä on useita, molempien reunojen kertoimien on vastattava toisiaan. ${\displaystyle e_{1}}$${\displaystyle e_{2}}$

Jos suunnatun graafin jokaisella reunalla on tällainen vastakkainen reuna graafissa, niin se on symmetrinen graafi .

Graafia, jonka solmujoukko on äärellinen, kutsutaan äärelliseksi graafiksi . Sitä vastoin graafia, jonka solmujoukko on ääretön, kutsutaan äärettömäksi graafiksi . Yleensä otetaan huomioon vain äärelliset graafit ja siksi jätetään pois attribuutti "finite", kun taas äärettömät graafit merkitään eksplisiittisesti.

Aligraafit, polut ja syklit

Suunnattu graafi ja sykli

Suunnattu graafi ilman sykliä

Graafin aligraafi sisältää vain solmut ja reunat, jotka myös sisältyvät . Solmujoukosta U indusoitu aligraafi sisältää U :n solmut ja kaikki G :n reunat näiden solmujen välillä. ${\displaystyle G'}$${\displaystyle G}$${\displaystyle G}$

Pareittain erillisten solmujen sarjaa , jossa peräkkäiset solmut ja graafissa on yhdistetty reunalla, kutsutaan poluksi , joskus myös poluksi . Jos , ja tämä on ainoa kaksoissolmu, sitä kutsutaan sykliksi tai ympyräksi . Vierekkäisten solmujen sekvenssiä, jossa solmut saavat toistaa, kutsutaan reunasekvenssiksi . Käsitteet tie, polku, reunasekvenssi, ympyrä ja sykli on joskus määritelty kirjallisuudessa eri tavalla. ${\displaystyle v_{1},\ldots ,v_{n}}$${\displaystyle v_{i}}$${\displaystyle v_{i+1}}$${\displaystyle v_{1}=v_{n}}$

Jos suunnattu graafi ei sisällä sykliä, sitä kutsutaan asykliseksi tai syklittömäksi – eli suunnatuksi asykliseksi graafiksi ( DAG, suunnattu asyklinen graafi ). Tällainen graafi voidaan laajentaa (äärelliseen ja diskreettiin) osittaiseen järjestykseen lisäämällä poluiksi kaikki reunat, joilla on samat aloitus- ja loppusolmut , eli lyhentämällä kiertoteitä muiden reunojen kautta kohdesolmuun . Tätä prosessia kutsutaan transitiivisen sulkeutumisen muodostukseksi . Hasse - kaavio on suunnattu asyklinen graafi, jossa transitiivisuuden lain mukaan implisiittiset reunat jätetään pois ( transitiivinen vähennys ).

Perustoiminnot

Graafin ominaisuuksia tarkasteltaessa käy usein niin, että graafiin joutuu soveltamaan yksinkertaisia ​​operaatioita voidakseen kirjoittaa mahdollisimman tiiviisti ja siten helpommin ymmärrettävästi. Joukkoteorian tavanomaisia ​​operaatioita (liitto, leikkaus, ero ja komplementti) sovelletaan erityisen usein graafien solmujoukkoon tai reunoihin, jolloin ne määritellään suoraan graafissa.

Ovat ja kuvaajat ovat samaa tyyppiä , niin merkitty ${\displaystyle G_{1}=(V_{1},E_{1})}$${\displaystyle G_{2}=(V_{2},E_{2})}$

• ${\displaystyle G_{1}+G_{2}}$kaavio, joka saadaan yhdistämällä joukko solmuja ja reunoja,
• ${\displaystyle G_{1}-E_{2}}$kaavio, joka saadaan vähentämällä ja reunajoukosta${\displaystyle E_{2}}$${\displaystyle G_{1}}$
• ${\displaystyle G_{1}-V_{2}}$graafi, joka saadaan vähentämällä kärkijoukosta ja poistamalla kaikki kärjet sisältävät reunat arvosta .${\displaystyle V_{2}}$${\displaystyle G_{1}}$${\displaystyle V_{2}}$

Huomaa joukon ja monijoukon termien liitto ja ero erilaiset määritelmät . Kirjoitat myös lyhennettynä

• ${\displaystyle G_{1}+E_{2}}$, jos on osajoukko ,${\displaystyle V_{2}}$${\displaystyle V_{1}}$
• ${\displaystyle G_{1}+V_{2}}$, jos on tyhjä tai osajoukko ,${\displaystyle E_{2}}$${\displaystyle E_{1}}$
• ${\displaystyle G_{1}+\{v,w\}}$, jos ,${\displaystyle G_{2}=(\{v,w\},\{\{v,w\}\})}$
• ${\displaystyle G_{1}+v}$, jos ,${\displaystyle G_{2}=(\{v\},\{\})}$
• ${\displaystyle G_{1}-\{v,w\}}$, jos ja${\displaystyle E_{2}=\{\{v,w\}\}}$
• ${\displaystyle G_{1}-v}$jos .${\displaystyle V_{2}=\{v\}}$

Reunojen supistuminen ja komplementtigraafin muodostaminen ovat muita perustoimintoja.

Huomautukset

Suuntaamattomat graafit ilman useita reunoja ovat hypergraafien erikoistapauksia. Multigrafit, joissa ei esiinny useita reunoja, eivät ole muodollisesti vastaavia graafien kanssa, joissa ei ole useita reunoja, mutta ne ovat deskriptiivisesti ekvivalentteja, minkä vuoksi niitä kutsutaan myös graafiksi ilman useita reunoja. Kahden muunnelman välillä on bijektiivinen kartoitus. Tässä mielessä graafit ilman useita reunoja ovat erikoistapauksia graafista, jossa on useita reunoja. Vastaavasti suuntaamattomat graafit ovat tietyssä mielessä suunnattujen graafien erikoistapauksia. Jos suunnattu graafi on symmetrinen ja ilman silmukoita, sitä kutsutaan myös suuntaamattomaksi , koska näiden kahden muunnelman välillä on myös yksinkertainen yksi-yhteen osoitus (katso myös viereisyysmatriisi ).

Tietenkin on myös mahdollista määritellä ohjaamattomia graafeja silmukoilla, jolloin ne on luultavasti helpoimmin määritelty suunnattujen graafien (muodollisiksi) erikoistapauksiksi ja silmukattomuuden ehto jätetään pois. Tällaiset graafit ovat kuitenkin harvoin graafiteorian harkinnan kohteena.

Yleisin graafityyppi on suunnattu hypergraafi , jossa on useita reunoja. Jokaista edellä määriteltyä kaaviotyyppiä voidaan sitten pitää tämän erikoistapauksena. Tällaisia ​​graafisia graafisia piirteitä ei kuitenkaan juuri koskaan tarkastella graafiteoriassa, minkä vuoksi niitä ei selitetä tässä tarkemmin.

Jos kaavioiden on tarkoitus toimia tosiasian esityksenä, tarvitaan algoritmeja, joita tarvitaan kaavioiden piirtämiseen . Tämä tietojenkäsittelytieteen tieteenala on edelleen kehittynyt viime vuosina ja tarjoaa ratkaisuja erilaisiin graafiin perustuviin visualisointeihin.

laajennuksia

Kaavioita voidaan täydentää lisäominaisuuksilla tai tiedoilla.

Värilliset kaaviot

Graafeiden laajennus solmuvärisiin kaavioihin saadaan täydentämällä monikko muodostamaan kolminkertainen . on kartoitus luonnollisten lukujen joukkoon . On selvää, että jokaiselle solmulle on annettu väri. ${\displaystyle G=(V,E)}$${\displaystyle (V,E)}$${\displaystyle (V,E,f)}$${\displaystyle f}$${\displaystyle V}$

Solmujen sijasta voidaan myös värjätä graafien reunat ilman useita reunoja ja hypergrafeissa ja sitten puhua reunavärisestä graafista . Tätä varten myös monikko laajennetaan kolmiosaiseksi , mutta missä on kartoitus numerosta (sen sijaan ) luonnollisten lukujen joukkoon . On selvää, että jokaiselle reunalle on annettu väri. Periaatteessa tämä on mahdollista myös monireunaisissa kaavioissa, mutta sitä on vaikeampi määritellä, varsinkin jos useille reunuksille on määrä antaa useita eri värejä niiden moninkertaisuuden mukaan. ${\displaystyle (V,E)}$${\displaystyle (V,E,f)}$${\displaystyle f}$${\displaystyle E}$${\displaystyle V}$

Huomaa, että termeillä "värjätä" ja "värjätä" on myös tarkempi merkitys graafiteoriassa. Täsmälleen yksi puhuu kelvollista väritystä , mutta yleensä jättää pois attribuutin "valid".

Vastaavasti on olemassa myös nimettyjä kaavioita , joissa solmuilla ja/tai reunoilla on nimi, ja kuvaukset tai solmut tai reunat antavat nimen. Aiemmin esitetyt esimerkit ovat nimettyjä kaavioita, joissa solmut on nimetty kirjaimilla. Tämä tehdään usein visualisoinneilla, jotta kaaviosta voidaan keskustella paremmin. ${\displaystyle (V,E,f,g)}$${\displaystyle f}$${\displaystyle g}$

Painotetut kaaviot

Solmu- tai reunavärillisten graafien sijaan puhutaan solmu- tai reunapainotetuista graafista, jos ne kartoitetaan luonnollisiin lukuihin, vaan ne kartoitetaan todellisiin lukuihin . Solmu- tai reunaväriset graafit ovat siksi solmu- tai reunapainotettujen graafien erikoistapauksia. ${\displaystyle f}$

Kutsumme tai myös solmun tai reunan painoa . Erottamiseksi puhutaan myös solmun painosta tai reunapainosta . Tällainen painotus tulee välttämättömäksi, kun tiedot solmusuhteista ovat riittämättömiä. Jos esimerkiksi tieverkostoa tarkastellaan (yksinkertaistettuna) graafina (paikat ovat solmuja, paikkoja yhdistävät kadut ovat reunoja), reunojen painotus voisi antaa tietoa kahden paikan välisestä etäisyydestä. Graafin reunapainot voidaan kerätä neliöpainomatriisiin, viereisyysmatriisiin .${\displaystyle f(v)}$${\displaystyle f(e)}$${\displaystyle v}$${\displaystyle e}$

Kartoituksia kaavioiden välillä

Lopuksi voidaan myös määritellä kuvaajien välisiä kartoituksia. Erityisen kiinnostavia ovat ne, jotka ovat yhteensopivia näiden kahden rakenteen kanssa , niin kutsutut "homomorfismit" .

Olkoon ja samantyyppisiä kuvaajia. Kartoitusta kutsutaan homomorfismiksi välillä ja jos : ${\displaystyle G_{1}=\left(V_{1},E_{1}\right)}$${\displaystyle G_{2}=\left(V_{2},E_{2}\right)}$ ${\displaystyle p\colon V_{1}\to V_{2}}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$

• Suuntaamattomissa graafisissa, joissa ei ole useita reunoja : Jos
  reuna , niin reuna .${\displaystyle \{v,w\}}$${\displaystyle G_{1}}$${\displaystyle \{p(v),p(w)\}}$${\displaystyle G_{2}}$
• Suunnatuissa kaavioissa, joissa ei ole useita reunoja: jos
  reuna , niin reuna .${\displaystyle (v,w)}$${\displaystyle G_{1}}$${\displaystyle (p(v),p(w))}$${\displaystyle G_{2}}$
• Suuntaamattomissa graafisissa useissa reunoissa : , i. H. mitkä tahansa kaksi kärkeä on yhdistetty enintään niin monella reunalla kuin niiden kuvapisteet.
  ${\displaystyle E_{1}(\{v,w\})\leq E_{2}(\{p(v),p(w)\})}$
• Suunnatuissa kaavioissa, joissa on useita reunoja: .
  ${\displaystyle E_{1}(v,w)\leq E_{2}(p(v),p(w))}$
• Suunnatuissa graafeissa, joissa on erilliset useat reunat: on assosioitunut kumppani ja kaikille reunoille ja ( ja niitä pidetään funktionaaleina, graafin homomorfismi on vain luonnollinen muunnos ).
  ${\displaystyle p}$${\displaystyle q\colon E_{1}\to E_{2}}$${\displaystyle e\in E_{1}}$${\displaystyle \mathrm {src} _{2}(q(e))=p(\mathrm {src} _{1}(e))}$${\displaystyle \mathrm {tgt} _{2}(q(e))=p(\mathrm {tgt} _{1}(e))}$${\displaystyle G_{1}}$${\displaystyle G_{2}}$
• Hypergrafeissa : jos reuna , niin reuna .
  ${\displaystyle \{v_{1},\cdots ,v_{k}\}}$${\displaystyle G_{1}}$${\displaystyle \{p(v_{1}),\cdots ,p(v_{k})\}}$${\displaystyle G_{2}}$

Kuva p ( G1 ₎ on tällöin G2 _: n osagraafi . Jos p on käännettävä ja käänteisfunktio on myös homomorfismi, niin p on graafien isomorfismi .

Huomaa, että kärjet ovat etusijalla reunoihin nähden määrittämällä p funktiona vain kärkipisteille , mikä vaikuttaa vain reunoihin.

kombinatoriikka

Yksinkertaisten suuntaamattomien graafien, joissa on solmuja , määrä kasvaa nopeasti solmujen määrän myötä ja on yhtä suuri kuin . Joten se kasvaa eksponentiaalisesti koko graafin reunojen lukumäärän mukaan . Jos solmuja ei ole numeroitu, eli isomorfisia graafeja ei lasketa, tämä luku on likimäärin verrannollinen , koska useimmissa isomorfismiluokissa kaikki numeroitujen solmujen permutaatiosta johtuvat graafit ovat erilaisia. Alla oleva taulukko näyttää tietokoneen käytön${\displaystyle n}$ ${\displaystyle 2^{\tfrac {n\cdot (n-1)}{2}}}$${\displaystyle {\tfrac {n\cdot (n-1)}{2}}}$ ${\displaystyle K_{n}}$${\displaystyle {\tfrac {1}{n!}}\cdot 2^{\tfrac {n\cdot (n-1)}{2}}}$${\displaystyle n!}$tietyt numerot : ^[6]${\displaystyle n\leq 8}$

Tietorakenteet

Suuntaamaton kaavio	viereisyysmatriisi
	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}}$

Graafeiden esittämiseen tietokoneessa on olennaisesti kaksi yleistä muotoa : viereisyysmatriisi (myös naapurimatriisi) ja viereisyysluettelo (naapuriluettelo). Kahden esityksen tärkeys piilee siinä, että käytännössä jokainen graafiteoreettisten ongelmien algoritminen ratkaisu pätee ainakin toiseen kahdesta esityksestä. Toinen, mutta harvemmin käytetty tapa esittää kuvaajia tietokoneessa on esiintymismatriisi , joka tunnetaan myös solmureunamatriisina.

Vaikka esiintymismatriisit ovat kalliimpia toteuttaa ja ylläpitää, ne tarjoavat joukon etuja viereisyysmatriiseihin verrattuna. Toisaalta kiinteällä määrällä reunoja ne vievät aina vain lineaarisen määrän tallennustilaa suhteessa solmujen määrään, mikä on erityisen edullista ohuille graafiille (eli graafiille, joissa on vähän reunaa), kun taas vierekkäisyysmatriisi vaatii neliötilaa suhteessa solmujen määrään (mutta on kompaktimpi tiheissä graafisissa eli monireunaisissa graafisissa). Toisaalta monet graafiteoreettiset ongelmat voidaan ratkaista vain vierekkäisyyslistoilla lineaarisessa ajassa . Käytännössä siis yleensä käytetään tätä esitystapaa.

ohjelmointi

Seuraava esimerkki C++- ohjelmointikielellä näyttää ohjatun graafin toteutuksen vierekkäisyysluetteloilla . Suunnattu graafi ilmoitetaan DirectedGraph - luokaksi . Päämenetelmää käytetään ohjelmaa suoritettaessa . ^[7]

#include <iostream> 

käyttäen nimiavaruutta std ;  

// Ilmoittaa datatyypin 
graafirakenteen  Solmu solmuille
{
    int indeksi ; 
    merkkijonoarvot ; _ 
    solmu * seuraava ; 
};

// Ilmoita tietotyyppi 
graafirakenteen  Edge reunuksille
{
    int aloitushakemisto ; 
    int endIndex ; 
};

// Ilmoita ohjatun graafin 
luokan  DirectedGraph luokka
{
julkinen :
    solmu ** headNode ; 

    // Tämä menetelmä lisää uuden solmun graafin viereisyysluetteloon ja palauttaa sen palautusarvona 
Node * insertNewNode ( int index , string value , Node * node )          
    {
        Node * newNode = uusi solmu ; // Luo uuden solmun tyyppiä Node newNode -> index = index ; // asettaa indeksin newNode -> arvo = arvo ; // asettaa arvon newNode -> next = node ; // asettaa osoittimen seuraajalle return newNode ;     
           
           
           
         
    }

    // konstruktori, joka luo suunnatun graafin annetuilla solmuilla ja reunoilla 
DirectedGraph ( Solmusolmut [ ], Edge edges [], int numberOfEdges , int numberOfNodes )           
    {
        headNode = uusi solmu * [ numberOfNodes ](); // alustaa osoittimien joukon solmuja varten ( int i = 0 ; i < numberOfEdges ; i ++ ) // silmukan iterointia varten graafin kaikkien reunojen yli {    
                 
        
            int startIndex = reunat [ i ]. startIndex ; // Reunan aloitussolmun indeksi int endIndex = reunat [ i ]. endIndex ; // Reunamerkkijonon loppusolmun indeksi = solmut [ endIndex ] . arvot ; // reunan loppusolmun arvo Solmu * newNode = insertNewNode ( endIndex , value , headNode [ startIndex ]);    
                
                
                  // kutsua insertNewNode-metodi lisätäksesi uuden solmun 
headNode [ startIndex ] = newNode ; // asettaa osoittimen uuteen solmuun }               
        
    }
};

// tulostaa konsolin kaikki vierekkäiset solmun solmut 
void writeAdjacencyList ( Node * node , int i )    
{
    cout << "solmu" << ( i + 1 ) << ":" ;        
    while ( solmu != nullptr )   
    {
        cout << "(" << solmu -> indeksi << ", " << solmu -> arvo << ")" ;          
        solmu = solmu -> seuraava ;  
    }
    cout << endl ;  
}

// päämenetelmä, joka suorittaa ohjelman 
int main () 
{
    // Ilmoittaa ja alustaa taulukot solmuille ja reunoille 
Solmusolmut [ ] = { { 0 , "A" },{ 1 , "B" },{ 2 , "C" },{ 3 , "D" },{ 4 , "E" } };         
    Reunareunat [ ] = { { 0 , 1 }, { 0 , 2 }, { 1 , 4 }, { 2 , 3 }, { 3 , 1 }, { 4 , 3 } };     
    int numberOfNodes = koko ( solmut ) / koko ( solmut [ 0 ]); // Hanki solmujen lukumäärä int numberOfEdges = sizeof ( reunat ) / sizeof ( reunat [ 0 ]); // Hae reunojen lukumäärä DirectedGraph directedGraph ( solmut , reunat , numberOfEdges , numberOfNodes ); // Luo suunnatun graafin annetuilla pisteillä ja reunoilla      
          
         
    for ( int i = 0 ; i < numberOfNodes ; i ++ ) // silmukan iterointiin graafin kaikkien solmujen läpi {         
    
        Node * headNode = suunnattuGraph . headNode [ i ];   
        writeAdjacencyList ( headNode , i ); // tulostaa solmun headNode viereisyysluettelon }  
    
}

Katso myös

• graafiset pelit
• Small World Phenomenon (Small World Network)
• Skaalaton verkko
• satunnainen kaavio
• vyöhykekaavio
• määräjärjestelmä

kirjallisuus

• Thomas H. Cormen, Charles Leiserson , Ronald L. Rivest , Clifford Stein: Algorithms - An Introduction . 2. painos. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8 , s. 531-533 . 
• Reinhard Diestel : Graafiteoria . 4. painos. Springer, Berlin et ai. 2010, ISBN 978-3-642-14911-5 ( verkossa: 4. sähköinen painos 2010, ilmainen esikatseluversio – ensimmäinen painos: 1996). 
• Jürgen Ebert: Tehokkaat kuvaajaalgoritmit . Julkaisussa: Study Texts – Computer Science . Akademische Verlags-Gesellschaft, Wiesbaden 1981, ISBN 3-400-00424-3 (samaan aikaan habilitaatiotutkielma Osnabrückin yliopistossa 1982). 
• Dieter Jungnickel : Kuvaajat, verkot ja algoritmit . 3. täysin tarkistettu ja laajennettu painos. BI-Wissenschafts-Verlag, Mannheim ja muut 1994, ISBN 3-411-14263-4 ( sisällysluettelo [PDF; 1.2 MB ]). 
• Manfred Nitzsche: Kaaviot aloittelijoille. Joulupukin talon ympärillä . Julkaisussa: Studies . 3. tarkistettu ja laajennettu painos. Vieweg+Teubner, Wiesbaden 2009, ISBN 978-3-8348-0813-4 . 

erittelyt

1. ↑ ^{a b c d} Reinhard Diestel : Graafiteoria . 4. painos. Springer, Berlin et ai. 2010, ISBN 978-3-642-14911-5 , s . 1–34 ( verkossa: 4. sähköinen painos 2010 – ensimmäinen painos: 1996). 
2. ↑ Suunnatut graafit . Julkaisussa: Claude Sammut, Geoffrey I. Webb (toim.): Encyclopedia of Machine Learning . Springer USA, 2010, s. 279 , doi : 10.1007/978-0-387-30164-8_218 . 
3. ↑ ^{a b} suunnatuille kaavioille: samaan suuntaan
4. ↑ [< https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-the-fundamental-theory-of-physics-and-its-beautiful/?dateline= ei >]
5. ↑ Brigitte Werners: Operaatiotutkimuksen perusteet . 3. painos. Springer, Berliini Heidelberg 2013, ISBN 978-3-642-40101-5 , s. 175-209 . 
6. ↑ Jakso A000088 OEIS : ssä
7. ↑ Ohjelmiston testausohje: Graafisen toteutus C++:ssa vierekkäisyysluettelon avulla

Tämä artikkeli on saatavilla äänitiedostona:

•  |
• Tallenna  |
• 26:00 min  |
• 12,3 Mt  |
• Puhutun version teksti (16.6.2022)

---

Lisätietoa puhutusta Wikipediasta