Grafen består av vertikaler och kanter. Hörnpunkterna är förbundna med kanter enligt en viss egenskap - förekomstförhållandet, som definierar uppsättningen kanter. I detta fall kan slingor och isolerade toppar bildas.
Bruksanvisning
1
Låt en uppsättning kanter på ett diagram anges och en relation som kan rita en kant från en topp till en annan. Som exempel är uppsättningen av vertikaler {1, 2, 3, 4, 5, 6, 7, 8}, de två topparna x och y i förhållandet x + y <8.
2
Bygg upp en vertikal adjacensmatris. För att göra detta, bygg ett fyrkantigt bord, antalet rader och kolumner i tabellen matchar antalet vertikaler. Sätt sedan 1 vid skärningspunkten mellan den i: e raden och den j: e kolumnen, om vertikalerna i och j uppfyller det givna 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 enligt följande:
1 + 1 <8, så i korsningen mellan den första raden och den första kolumnen är 1
1 + 2 <8, igen 1
1 + 3 <8, igen 1
…
1 + 7 <8, felaktig ojämlikhet, då kommer tabellelementet att vara 0
1 + 8 <8, igen 0
3
För att ta reda på antalet kanter räknar du antalet enheter i anliggningsmatrisen medan du inte rippar kanterna.
I exemplet erhölls en symmetrisk matris, därför beräknades enheterna först över huvudmatrisen i matrisen (markerad med blått) och sedan enheterna på huvuddiagonalen (markerad med rött). Det totala antalet revben är 12.
4
Bygg en matris av incidenter (kanter). För att göra detta, rita en tabell, antalet rader i det är lika med antalet vertiklar i diagrammet och antalet kolumner är lika med antalet kanter. Sätt enheterna i linjerna som kommer att anslutas med en kant. De kanter som leder uppifrån till den kallas slingor och läggs till i slutet av matrisen. I de kolumner som motsvarar slingorna finns det bara en enhet, till skillnad från de andra kanterna.
5
Rita nu en graf. Ordna topparna på papperet godtyckligt och anslut dem med kanterna med de konstruerade tabellerna. Hörn som inte är anslutna med kanter kallas isolerade.
Var uppmärksam
Figuren visar revbenen för tydlighet. Vanligtvis skrivs vikten på ribben över revbenet.
