Diagrammet består av hörn och kanter. Hörnpunkterna är förbundna med kanter enligt en viss egenskap - incidensrelationen, som definierar uppsättningen kanter. I detta fall kan öglor och isolerade hörn bildas.
Instruktioner
Steg 1
Låt uppsättningen av kantskant anges i grafen och förhållandet längs vilket det är möjligt att rita en kant från ett toppunkt till ett annat ges. Som ett exempel är uppsättningen av hörn {1, 2, 3, 4, 5, 6, 7, 8}, två hörn x och y i förhållandet x + y <8.
Steg 2
Bygg en vertex-angränsande matris. För att göra detta, bygg en fyrkantig tabell, antalet rader och kolumner i tabellen sammanfaller med antalet hörnpunkter. Sätt sedan 1 i skärningspunkten mellan den i: a raden och den j: e kolumnen om hörnarna i och j uppfyller det angivna förhållandet. Sätt 0 vid skärningspunkten mellan den i: e raden och den j: e kolumnen om förhållandet för motsvarande element inte uppfylls.
I vårt exempel fylls den första raden i enligt följande:
1 + 1 <8, så det finns 1 i korsningen mellan 1: a raden och 1: a kolumnen
1 + 2 <8, igen 1
1 + 3 <8, igen 1
1 + 7 <8, felaktig ojämlikhet, så detta element i tabellen blir 0
1 + 8 <8, igen 0
Steg 3
För att ta reda på antalet kanter räknar du antalet av dem i angränsningsmatrisen utan att duplicera kanterna.
I exemplet erhölls en symmetrisk matris, så vi räknade först de ovanför matrisens huvuddiagonal (markerade i blått) och sedan de på huvuddiagonalen (markerade med rött). Det totala antalet revben är 12.
Steg 4
Bygg en matris av incidenter (kanter). För att göra detta, rita en tabell, antalet rader i den är lika med antalet hörn i diagrammet och antalet kolumner är lika med antalet kanter. Sätt enheter på de linjer som kommer att anslutas med en kant. Kanterna som leder från toppunkten till det kallas loopar och läggs till i slutet av matrisen. I kolumnerna som motsvarar öglorna finns det bara en enhet, i motsats till resten av kanterna.
Steg 5
Rita nu ett diagram. Placera topparna på papperet på något sätt och anslut dem med kanterna med hjälp av de konstruerade tabellerna. Hörn som inte är förbundna med kanter kallas isolerade.
