Grafen består av hjørner og kanter. Høydepunktene er forbundet med kanter i henhold til en viss egenskap - forekomstforholdet, som definerer settet med kanter. I dette tilfellet kan det dannes løkker og isolerte hjørner.
Bruksanvisning
1
La et sett med kanter på en graf bli gitt og en relasjon gitt der man kan tegne en kant fra en toppunkt til en annen. Som et eksempel er settet med toppunktene {1, 2, 3, 4, 5, 6, 7, 8}, de to toppunktene x og y i forholdet x + y <8.
2
Bygge en verteks adjacency matrise. For å gjøre dette, bygg et firkantet bord, antall rader og kolonner i tabellen samsvarer med antall vertikater. Sett deretter 1 i skjæringspunktet mellom den i-th raden og den j-th kolonnen, hvis toppunktene i og j tilfredsstiller det gitte forholdet. Sett 0 i skjæringspunktet mellom den i-de raden og den j-th kolonnen, hvis forholdet for de tilsvarende elementene ikke er oppfylt.
I vårt eksempel fylles den første linjen som følger:
1 + 1 <8, så i skjæringspunktet mellom 1. rad og 1. kolonne er 1
1 + 2 <8, igjen 1
1 + 3 <8, igjen 1
…
1 + 7 <8, feil ulikhet, da vil dette tabellelementet være 0
1 + 8 <8, igjen 0
3
For å finne ut hvor mange kanter, teller du antall enheter i adjacency-matrisen, uten å rive kantene.
I eksemplet ble en symmetrisk matrise oppnådd, derfor ble enhetene først beregnet over hoveddiagonalen til matrisen (markert i blått), og deretter enhetene på hoveddiagonalen (markert med rødt). Det totale antall ribbe er 12.
4
Bygg en matrise av hendelser (kanter). For å gjøre dette, tegner du en tabell, antall rader i den er lik antallet vertekser på grafen, og antall kolonner er lik antall kanter. Sett enhetene i linjene som skal kobles sammen med en kant. Kantene som fører fra toppen til den kalles løkker og legges til enden av matrisen. I kolonnene som tilsvarer løkkene, er det bare en enhet, i motsetning til de andre kantene.
5
Tegn nå en graf. Arranger toppunktene på papir vilkårlig og koble dem til kantene ved hjelp av de konstruerte tabellene. Vertikaler som ikke er koblet sammen med kanter kalles isolert.
Vær oppmerksom
Figuren viser ribbeina for klarhet. Vanligvis skrives vekten på ribben over ribben.
