Grafen består av hjørner og kanter. Hjørnepunktene er forbundet med kanter i henhold til en bestemt egenskap - innfallssammenheng, som definerer settet med kanter. I dette tilfellet kan det dannes løkker og isolerte hjørner.
Bruksanvisning
Trinn 1
La settet med kanter på grafen gis og forholdet det er mulig å tegne en kant fra et toppunkt til et annet er gitt. Som et eksempel er settet med hjørner {1, 2, 3, 4, 5, 6, 7, 8}, to hjørner x og y i forholdet x + y <8.
Steg 2
Bygg en toppunkt-tilstøtende matrise. For å gjøre dette, bygg en firkantet tabell, antall rader og kolonner i tabellen sammenfaller med antall hjørner. Sett deretter 1 i skjæringspunktet mellom i-rad og j-kolonne hvis hjørnene i og j tilfredsstiller det gitte forholdet. Sett 0 i skjæringspunktet mellom den i-rad og j-kolonne hvis forholdet for de tilsvarende elementene ikke er oppfylt.
I vårt eksempel er den første linjen fylt ut som følger:
1 + 1 <8, så det er 1 i krysset mellom 1. rad og 1. kolonne
1 + 2 <8, igjen 1
1 + 3 <8, igjen 1
1 + 7 <8, feil ulikhet, så dette elementet i tabellen vil være 0
1 + 8 <8, igjen 0
Trinn 3
For å finne ut antall kanter, teller du antallet av dem i tilknytningsmatrisen uten å duplisere kantene.
I eksemplet ble det oppnådd en symmetrisk matrise, så vi telte først de over matrisens hoveddiagonal (markert i blått), og deretter de på hoveddiagonalen (merket med rødt). Totalt antall ribber er 12.
Trinn 4
Bygg en matrise av hendelser (kanter). For å gjøre dette, tegne en tabell, antall rader i den er lik antall hjørner i grafen, og antall kolonner er lik antall kanter. Sett enheter på de linjene som vil være forbundet med en kant. Kantene som fører fra toppunktet til det kalles løkker og legges til enden av matrisen. I kolonnene som tilsvarer løkkene, er det bare en enhet, i motsetning til resten av kantene.
Trinn 5
Tegn nå en graf. Plasser toppunktene på papiret på noen måte og koble dem med kanter ved hjelp av de konstruerte bordene. Vertices som ikke er forbundet med kanter kalles isolerte.
