El gràfic consta de vèrtexs i arestes. Els vèrtexs estan connectats per arestes segons una propietat determinada: la relació d’incidència, que defineix el conjunt d’arestes. En aquest cas, es poden formar bucles i vèrtexs aïllats.
Instruccions
Pas 1
Donem el conjunt d’arestes del gràfic i es dóna la relació al llarg de la qual és possible dibuixar una vora d’un vèrtex a un altre. Com a exemple, el conjunt de vèrtexs {1, 2, 3, 4, 5, 6, 7, 8}, dos vèrtexs x i y tenen la proporció x + y <8.
Pas 2
Construeix una matriu d’adjacència del vèrtex. Per fer-ho, creeu una taula quadrada, el nombre de files i columnes de la taula coincideix amb el nombre de vèrtexs. A continuació, poseu 1 a la intersecció de la i-a fila i la j-columna si els vèrtexs i i satisfan la proporció donada. Poseu 0 a la intersecció de la i-e fila i la j-columna si no es compleix la proporció dels elements corresponents.
En el nostre exemple, la primera línia s’omple de la següent manera:
1 + 1 <8, de manera que n'hi ha 1 a la intersecció de la 1a fila i la 1a columna
1 + 2 <8, de nou 1
1 + 3 <8, de nou 1
1 + 7 <8, desigualtat incorrecta, de manera que aquest element de la taula serà 0
1 + 8 <8, de nou 0
Pas 3
Per esbrinar el nombre d’arestes, compteu el nombre d’unes a la matriu d’adjacència sense duplicar les arestes.
En l'exemple, es va obtenir una matriu simètrica, de manera que vam comptar primer els que es trobaven per sobre de la diagonal principal de la matriu (marcats en blau), i després els de la diagonal principal (marcats en vermell). El nombre total de costelles és de 12.
Pas 4
Construeix una matriu d'incidents (arestes). Per fer-ho, dibuixeu una taula, el nombre de files que hi ha és igual al nombre de vèrtexs del gràfic i el nombre de columnes és igual al nombre d’arestes. Poseu unitats a les línies que estaran connectades per una vora. Les vores que condueixen des del vèrtex fins a ell s’anomenen bucles i s’afegeixen al final de la matriu. A les columnes corresponents als bucles, només hi ha una unitat, en contrast amb la resta de vores.
Pas 5
Ara dibuixa un gràfic. Col·loqueu els vèrtexs sobre el paper de qualsevol manera i connecteu-los amb vores mitjançant les taules construïdes. Els vèrtexs que no estan connectats per arestes s’anomenen aïllats.
