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 .
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 .
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
,eli joukko koostuu joukon 2-alkioisista osajoukoista .
Aiheeseen liittyvät termit
Graafiteorialla ei ole vakiintunutta terminologiaa. Tästä syystä joissakin julkaisuissa voidaan käyttää muita kuin alla lueteltuja termejä.
Tyypillisesti graafi kuvataan kaaviona : kärjet - pisteet, reunat - viivat.
Pseudografi on kahden joukon kokoelma - ei-tyhjä joukko ja joukko joukon järjestämättömiä elementtipareja .
Elementti on sallittu pseudografin reunojen joukossa .
Toisin sanoen, jos joukon E alkiot voivat olla silmukoita, niin graafia kutsutaan pseudografiksi [2] .
Multigrafi on kahden joukon kokoelma - ei-tyhjä joukko ja joukko joukon eri elementtien järjestämättömiä pareja .
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] .
Pseudomultigrafi on kokoelma kahdesta joukosta - ei-tyhjästä joukosta ja joukon järjestämättömien elementtiparien monijoukosta .
Toisin sanoen, jos perhe, joka sisältää samat elementit (useita särmiä) ja voi sisältää silmukoita, graafia kutsutaan pseudomultigrafiksi [2] .
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ä
.yhdessä kahden näytön kanssa
,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
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.
.yhdessä kahden näytön kanssa
Suunnatut ja suuntaamattomat graafit ovat sekagraafien erikoistapauksia.
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.
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.
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:
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.
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ä.
Graafin reunaa kutsutaan sillaksi, jos sen poistaminen lisää komponenttien määrää.
Kaaviota kutsutaan:
Tapahtuu myös:
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:
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.
Taulukko, jossa rivit vastaavat graafin kärkipisteitä ja sarakkeet vastaavat kaavion linkkejä (reunoja). Matriisisoluun rivin ja sarakkeen leikkauskohdassa kirjoitetaan seuraava:
yksi jos yhteys "poistuu" ylhäältä , -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).
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 :.
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".
Luettelo, jossa jokainen graafin reuna vastaa merkkijonoa, joka tallentaa kaksi reunaan sattuvaa kärkeä.
Muistin koko :.
Tämä on kompaktin tapa esittää kuvaajia, joten sitä käytetään usein ulkoiseen tallennustilaan tai tiedonvaihtoon.
Konekäsittelyyn soveltuvien ja samalla ihmisen havainnointiin sopivien kuvaajien kuvaamiseen käytetään useita standardoituja kieliä, mukaan lukien:
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 .
VisualisointiohjelmatSeuraavia ohjelmistotyökaluja käytetään kaavioiden visualisointiin :