Le graphe est constitué de sommets et d'arêtes. Les sommets sont reliés par des arêtes selon une certaine propriété - la relation d'incidence, qui définit l'ensemble des arêtes. Dans ce cas, des boucles et des sommets isolés peuvent se former.
Instructions
Étape 1
Soit l'ensemble des arêtes du graphe donné et la relation le long de laquelle il est possible de tracer une arête d'un sommet à un autre est donnée. A titre d'exemple, l'ensemble des sommets {1, 2, 3, 4, 5, 6, 7, 8}, deux sommets x et y sont dans le rapport x + y <8.
Étape 2
Construire une matrice d'adjacence de sommets. Pour ce faire, construisez un tableau carré, le nombre de lignes et de colonnes du tableau coïncide avec le nombre de sommets. Ensuite, mettez 1 à l'intersection de la i-ème ligne et de la j-ème colonne si les sommets i et j satisfont le rapport donné. Mettez 0 à l'intersection de la i-ème ligne et de la j-ème colonne si le rapport pour les éléments correspondants n'est pas respecté.
Dans notre exemple, la première ligne est remplie comme suit:
1 + 1 <8, donc il y a 1 à l'intersection de la 1ère ligne et de la 1ère colonne
1 + 2 <8, encore 1
1 + 3 <8, encore 1
1 + 7 <8, inégalité incorrecte, donc cet élément du tableau sera 0
1 + 8 <8, encore 0
Étape 3
Pour connaître le nombre d'arêtes, comptez le nombre de uns dans la matrice d'adjacence sans dupliquer les arêtes.
Dans l'exemple, une matrice symétrique a été obtenue, nous avons donc compté d'abord celles situées au-dessus de la diagonale principale de la matrice (marquées en bleu), puis celles situées sur la diagonale principale (marquées en rouge). Le nombre total de côtes est de 12.
Étape 4
Construire une matrice d'incidents (edges). Pour ce faire, dessinez un tableau, le nombre de lignes qu'il contient est égal au nombre de sommets du graphique et le nombre de colonnes est égal au nombre d'arêtes. Mettez des unités sur ces lignes qui seront reliées par une arête. Les arêtes menant du sommet à celui-ci sont appelées boucles et sont ajoutées à la fin de la matrice. Dans les colonnes correspondant aux boucles, il n'y a qu'une seule unité, contrairement au reste des bords.
Étape 5
Tracez maintenant un graphique. Placez les sommets sur le papier de quelque manière que ce soit et reliez-les aux bords à l'aide des tables construites. Les sommets qui ne sont pas connectés par des arêtes sont appelés isolés.
