Grafen består af hjørner og kanter. Hovedpunkterne er forbundet med kanter i henhold til en bestemt egenskab - incidensrelationen, der definerer kantsættet. I dette tilfælde kan der dannes sløjfer og isolerede hjørner.
Instruktioner
Trin 1
Lad grafens kantsæt angives, og forholdet, langs hvilket det er muligt at tegne en kant fra et toppunkt til et andet, gives. Som et eksempel er sæt af hjørner {1, 2, 3, 4, 5, 6, 7, 8}, to hjørner x og y i forholdet x + y <8.
Trin 2
Byg en toppunkt-tilstødende matrix. For at gøre dette skal du oprette en firkantet tabel, antallet af rækker og kolonner i tabellen falder sammen med antallet af hjørner. Sæt derefter 1 i skæringspunktet mellem den i-række og j-kolonne, hvis hjørnerne i og j opfylder det givne forhold. Sæt 0 i skæringspunktet mellem den i-række og j-kolonne, hvis forholdet for de tilsvarende elementer ikke er opfyldt.
I vores eksempel udfyldes den første linje som følger:
1 + 1 <8, så der er 1 ved skæringspunktet mellem 1. række og 1. kolonne
1 + 2 <8, igen 1
1 + 3 <8, igen 1
1 + 7 <8, forkert ulighed, så dette element i tabellen vil være 0
1 + 8 <8, igen 0
Trin 3
For at finde ud af antallet af kanter skal du tælle antallet af dem i nærhedsmatrixen uden at duplikere kanterne.
I eksemplet blev der opnået en symmetrisk matrix, så vi tællede først dem over matrixens hoveddiagonal (markeret med blåt) og derefter dem på hoveddiagonalen (markeret med rødt). Det samlede antal ribben er 12.
Trin 4
Byg en matrix af hændelser (kanter). For at gøre dette skal du tegne en tabel, antallet af rækker i det er lig med antallet af hjørner i grafen, og antallet af kolonner er lig med antallet af kanter. Sæt enheder på de linjer, der er forbundet med en kant. Kanterne, der fører fra toppunktet til det, kaldes sløjfer og føjes til slutningen af matrixen. I kolonnerne svarende til løkkerne er der kun en enhed i modsætning til resten af kanterne.
Trin 5
Tegn nu en graf. Placer hjørnerne på papiret på nogen måde, og forbind dem med kanter ved hjælp af de konstruerede tabeller. Højdepunkter, der ikke er forbundet med kanter, kaldes isolerede.
