A Ohjaamattomat graafit : Kaavio, jossa reunoilla ei ole suuntaa, eli reunoissa ei ole kulkusuuntaa osoittavia nuolia. Esimerkki: Sosiaalisen verkoston kaavio, jossa ystävyyssuhteet eivät ole suuntaa antavia.

Ohjatut graafit : Kaavio, jossa reunoilla on suunta, eli reunoissa on nuolet, jotka osoittavat kulkusuunnan. Esimerkki: Verkkosivukaavio, jossa sivujen väliset linkit ovat suuntaavia.

Painotetut kaaviot: Kaavio, jossa reunoihin liittyy painoja tai kustannuksia. Esimerkki: Tieverkoston kaavio, jossa painot voivat edustaa kahden kaupungin välistä etäisyyttä.

Painottamaton kaavio s: Kaavio, jossa reunoilla ei ole painoja tai kustannuksia. Esimerkki: Sosiaalisen verkoston kaavio, jossa reunat edustavat ystävyyssuhteita.

Täydelliset kaaviot: Kaavio, jossa jokainen kärkipiste on yhteydessä jokaiseen toiseen kärkeen. Esimerkki: Turnauskaavio, jossa jokainen pelaaja pelaa jokaista toista pelaajaa vastaan.

Kaksiosaiset kaaviot: Graafi, jossa kärjet voidaan jakaa kahteen disjunktiseen joukkoon siten, että jokainen reuna yhdistää yhden joukon kärjen toisen joukon kärkeen. Esimerkki: Työnhakijakaavio, jossa pisteet voidaan jakaa työnhakijoihin ja avoimiin työpaikkoihin.

puut : Yhdistetty kaavio, jossa ei ole jaksoja. Esimerkki: Sukupuu, jossa jokainen henkilö on yhteydessä vanhempiinsa.

Pyörät : Kaavio, jossa on vähintään yksi sykli. Esimerkki: Pyörän yhteiskäyttökaavio, jossa pyörät edustavat polkupyörien kulkemia reittejä.

Harvat kaaviot: Graafi, jossa on suhteellisen vähän reunoja verrattuna pisteiden määrään. Esimerkki: Kemiallinen reaktiokaavio, jossa jokainen kärki edustaa kemiallista yhdistettä ja jokainen reuna edustaa kahden yhdisteen välistä reaktiota.

Tiheä graafi s: Graafi, jossa on useita reunoja verrattuna pisteiden määrään. Esimerkki: Sosiaalisen verkoston graafi, jossa jokainen kärki edustaa henkilöä ja jokainen reuna edustaa ystävyyttä.

Graafityypit:

1. Äärilliset kuvaajat

Graafin sanotaan olevan äärellinen, jos sillä on äärellinen määrä pisteitä ja äärellinen määrä reunoja. Äärillinen graafi on graafi, jossa on äärellinen määrä pisteitä ja kulmia. Toisin sanoen äärellisen graafin sekä kärkien lukumäärä että reunojen määrä ovat rajoitettuja ja ne voidaan laskea. Äärillisiä kaavioita käytetään usein mallintamaan todellisia tilanteita, joissa on rajoitettu määrä objekteja ja suhteita

2. Ääretön kuvaaja:

Graafin sanotaan olevan ääretön, jos sillä on ääretön määrä pisteitä ja ääretön määrä reunoja.

3. Triviaalikaavio:

Graafin sanotaan olevan triviaali, jos äärellinen graafi sisältää vain yhden kärjen eikä yhtään reunaa. Triviaaligraafi on graafi, jossa on vain yksi kärki ja ei kulmia. Se tunnetaan myös singleton-graafina tai yksipistegraafina. Triviaalikaavio on yksinkertaisin graafityyppi, ja sitä käytetään usein lähtökohtana monimutkaisempien graafien rakentamiseen. Graafiteoriassa triviaaleja kuvaajia pidetään rappeutuneena tapauksena, eikä niitä tyypillisesti tutkita yksityiskohtaisesti

df loc

4. Yksinkertainen kaavio:

Yksinkertainen graafi on graafi, jossa ei ole enempää kuin yksi reuna kärkiparien välillä. Yksinkertainen eri kaupunkeja yhdistävä rata on esimerkki yksinkertaisesta kaaviosta.

5. Monikuvaaja:

Mitä tahansa graafia, joka sisältää joitakin yhdensuuntaisia ​​reunoja, mutta ei sisällä itsesilmukkaa, kutsutaan multigrafiksi. Esimerkiksi tiekartta.

• Rinnakkaiset reunat: Jos kaksi kärkeä on yhdistetty useampaan kuin yhteen reunaan, tällaisia ​​reunoja kutsutaan rinnakkaisiksi reunoiksi, jotka ovat useita reittejä mutta yksi kohde.
• Silmukka: Kuvaajan reunaa, joka alkaa kärjestä ja päättyy samaan kärkeen, kutsutaan silmukaksi tai itsesilmukaksi.

6. Nollakaavio:

Graafi, jonka kertaluku on n ja koko on nolla, on graafi, jossa on vain erillisiä pisteitä, joissa ei ole mitään kärkiparia yhdistäviä reunoja. Nollagraafi on graafi, jossa ei ole reunoja. Toisin sanoen se on graafi, jossa on vain kärjet, eikä niiden välillä ole yhteyksiä. Nollagraafia voidaan kutsua myös reunattomaksi graafiksi, eristettyksi graafiksi tai diskreetiksi graafiksi

7. Täydellinen kaavio:

Yksinkertaista graafia, jossa on n pistettä, kutsutaan täydelliseksi graafiksi, jos kunkin kärjen aste on n-1, eli yksi kärki on kiinnitetty n-1 reunalla tai muilla graafin pisteillä. Täydellistä kuvaajaa kutsutaan myös nimellä Full Graph.

8. Pseudokaavio:

Graafia G, jossa on itsesilmukka ja useita reunoja, kutsutaan pseudograafiksi. Pseudografi on graafin tyyppi, joka mahdollistaa itsesilmukat (reunat, jotka yhdistävät kärjen itseensä) ja useita reunoja (useampi kuin yksi reuna, joka yhdistää kaksi kärkeä). Sen sijaan yksinkertainen graafi on graafi, joka ei salli silmukoita tai useita reunoja.

9. Säännöllinen kaavio:

Yksinkertaisen graafin sanotaan olevan säännöllinen, jos graafin G kaikki kärjet ovat yhtä suuria. Kaikki täydelliset kaaviot ovat säännöllisiä, mutta päinvastoin ei ole mahdollista. Säännöllinen graafi on suuntaamaton graafi, jossa jokaisessa kärjessä on sama määrä reunoja tai naapureita. Toisin sanoen, jos graafi on säännöllinen, niin jokaisella kärjellä on sama aste.

10. Kaksiosainen kaavio:

Graafin G = (V, E) sanotaan olevan kaksiosainen graafi, jos sen kärkijoukko V(G) voidaan jakaa kahteen ei-tyhjään disjointtiin. V1(G) ja V2(G) siten, että kunkin E(G):n reunan e toinen pää on kohdassa V1(G) ja toinen pää kohdassa V2(G). Osiota V1 U V2 = V kutsutaan G:n kaksiosaiseksi. Tässä kuvassa: V1(G)={V5, V4, V3} ja V2(G)={V1, V2}

katodisädeputkimonitori

11. Merkitty kaavio:

Jos graafin kärjet ja reunat on merkitty nimellä, päivämäärällä tai painolla, sitä kutsutaan nimetyksi graafiksi. Sitä kutsutaan myös painotetuksi kuvaajaksi.

12. Digraafikaavio:

Graafia G = (V, E), jonka kuvaus f on sellainen, että jokainen reuna kuvataan jollekin järjestetylle pisteparille (Vi, Vj), kutsutaan digrafiksi. Sitä kutsutaan myös Ohjattu graafi . Järjestetty pari (Vi, Vj) tarkoittaa Vi:n ja Vj:n välistä reunaa, jossa on Vi:stä Vj:ään suunnattu nuoli. Tässä kuvassa: e1 = (V1, V2) e2 = (V2, V3) e4 = (V2, V4)

13. Alakaavio:

Graafia G1 = (V1, E1) kutsutaan graafin G(V, E) osagraafiksi, jos V1(G) on V(G):n osajoukko ja E1(G) on E(G):n osajoukko siten, että jokaisella G1:n reunalla on samat päätypisteet kuin G:ssä.

14. Yhdistetty tai irrotettu kaavio:

Graafin G sanotaan olevan yhteydessä, jos mikä tahansa graafin G kärkipari (Vi, Vj) on saavutettavissa toisistaan. Tai graafin sanotaan olevan yhdistetty, jos graafin G jokaisen kärkiparin välillä on vähintään yksi polku, muuten se on irti. Nollagraafi, jossa on n kärkeä, on irrotettu graafi, joka koostuu n komponentista. Jokainen komponentti koostuu yhdestä kärjestä, eikä siinä ole reunaa.

15. Syklinen kaavio:

Graafi G, joka koostuu n pisteestä ja n> = 3 eli V1, V2, V3- – – – Vn ja reunat (V1, V2), (V2, V3), (V3, V4)- – – – (Vn, V1) kutsutaan syklisiksi graafiksi.

16. Alagraafien tyypit:

• Vertexin disjunktiosagraafi: Minkä tahansa kahden graafin G1 = (V1, E1) ja G2 = (V2, E2) sanotaan olevan graafin G = (V, E) kärkihajoja, jos V1(G1) -leikkaus V2(G2) = nolla. Kuvassa G1:n ja G2:n välillä ei ole yhteistä kärkeä.
• Reunan disjunktiosagraafi: Aligraafin sanotaan olevan reuna-disjunkti, jos E1(G1)-leikkaus E2(G2) = nolla. Kuvassa G1:n ja G2:n välillä ei ole yhteistä reunaa.

Huomautus: Edge-disjoint-aligraafilla voi olla yhteisiä kärkipisteitä, mutta vertex-disjunktigrafilla ei voi olla yhteistä reunaa, joten kärkidisjoint-aligraafi on aina reuna-disjunkti-aligraafi.

17. Virtaava aligraafi

Tarkastellaan kuvaajaa G(V,E) alla olevan kuvan mukaisesti. Virtaava aligraafi on osagraafi, joka sisältää kaikki alkuperäisen graafin G kärjet, joka on G'(V',E') ulottuu, jos V'=V ja E' on E:n osajoukko.

Joten yksi virittävistä aligraafista voi olla kuten G'(V',E') alla on esitetty. Siinä on kaikki alkuperäisen graafin G kärjet ja osa G:n reunoista.

Tämä on vain yksi monista graafin G ulottuvista osagraafista. Voimme luoda useita muita ulottuvia aligraafia erilaisilla reunojen yhdistelmillä. Huomaa, että jos tarkastelemme graafia G'(V',E'), jossa V'=V ja E'=E, niin graafi G' on graafin G(V,E) ulottuva osagraafi.

Graafisten edut:

1. Graafeja voidaan käyttää monimutkaisten järjestelmien ja suhteiden mallintamiseen ja analysointiin.
2. Ne ovat hyödyllisiä tietojen visualisoinnissa ja ymmärtämisessä.
3. Graafialgoritmeja käytetään laajalti tietojenkäsittelytieteessä ja muilla aloilla, kuten sosiaalisten verkostojen analysoinnissa, logistiikassa ja kuljetuksissa.
4. Kaavioita voidaan käyttää esittämään monenlaisia ​​tietotyyppejä, mukaan lukien sosiaaliset verkostot, tieverkot ja Internet.

Graafisten miinukset:

1. Suuria kaavioita voi olla vaikea visualisoida ja analysoida.
2. Graafialgoritmit voivat olla laskennallisesti kalliita, etenkin suurille kaavioille.
3. Graafisten tulosten tulkinta voi olla subjektiivista ja saattaa vaatia aluekohtaista tietoa.
4. Kaaviot voivat olla herkkiä kohinalle ja poikkeaville arvoille, mikä voi vaikuttaa analyysitulosten tarkkuuteen.

Aiheeseen liittyvä artikkeli: Grafin sovellukset, edut ja haitat