Kaavio koostuu kärjistä ja reunoista. Pisteet yhdistetään reunoilla tietyn ominaisuuden mukaan - esiintyvyyssuhde, joka määrittää reunaryhmän. Tässä tapauksessa silmukoita ja eristettyjä pisteitä voi muodostua.
Ohjeet
Vaihe 1
Annetaan graafin reunaryhmä ja annetaan suhde, jota pitkin on mahdollista piirtää reuna yhdestä kärjestä toiseen. Esimerkkinä pisteiden joukko {1, 2, 3, 4, 5, 6, 7, 8}, kaksi kärkeä x ja y ovat suhteessa x + y <8.
Vaihe 2
Rakenna kärkipisteen vierekkäisyysmatriisi. Voit tehdä tämän rakentamalla neliön muotoisen taulukon, taulukon rivien ja sarakkeiden määrä on sama kuin kärkipisteiden määrä. Laita sitten 1 i: nnen rivin ja j: nnen sarakkeen leikkauspisteeseen, jos pisteet i ja j täyttävät annetun suhteen. Laita 0 i: n ja j: nnen sarakkeen leikkauspisteeseen, jos vastaavien elementtien suhde ei täyty.
Esimerkissämme ensimmäinen rivi täytetään seuraavasti:
1 + 1 <8, joten ensimmäisen rivin ja ensimmäisen sarakkeen risteyksessä on 1
1 + 2 <8, jälleen 1
1 + 3 <8, jälleen 1
1 + 7 <8, väärä epätasa-arvo, joten taulukon tämä elementti on 0
1 + 8 <8, jälleen 0
Vaihe 3
Jos haluat selvittää reunojen lukumäärän, laske niiden lukumäärä vierekkäisyysmatriisiin kopioimatta reunoja.
Esimerkissä saatiin symmetrinen matriisi, joten laskimme ensin matriisin päädiagonaalin yläpuolella olevat (merkitty sinisellä) ja sitten päädiagonaalin (punaisella merkityt). Kylkiluiden kokonaismäärä on 12.
Vaihe 4
Rakenna matriisi tapahtumista (reunat). Tätä varten piirretään taulukko, siinä olevien rivien lukumäärä on yhtä suuri kuin kaavion pisteiden määrä ja sarakkeiden määrä on yhtä suuri kuin reunojen lukumäärä. Laita yksiköt niille viivoille, jotka liitetään reunalla. Kärkipisteestä siihen johtavia reunoja kutsutaan silmukoiksi ja lisätään matriisin päähän. Silmukoita vastaavissa sarakkeissa on vain yksi yksikkö, toisin kuin muut reunat.
Vaihe 5
Piirrä nyt kaavio. Aseta pisteet paperille millään tavalla ja yhdistä ne reunoihin käyttämällä rakennettuja taulukoita. Pisteitä, joita ei ole yhdistetty reunoilla, kutsutaan eristetyiksi.
