Le graphique est composé 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.
Manuel d'instructions
1
Soit un ensemble d'arêtes d'un graphe donné et une relation donnée par laquelle on peut dessiner une arête d'un sommet à un autre. Par exemple, l'ensemble des sommets {1, 2, 3, 4, 5, 6, 7, 8}, les deux sommets x et y sont dans le rapport x + y <8.
2
Construisez une matrice d'adjacence de vertex. Pour ce faire, créez un tableau carré, le nombre de lignes et de colonnes du tableau correspond au nombre de sommets. Mettez ensuite 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 satisfait.
Dans notre exemple, la première ligne est remplie comme suit:
1 + 1 <8, donc à l'intersection de la 1ère ligne et de la 1ère colonne est 1
1 + 2 <8, encore 1
1 + 3 <8, encore 1
…
1 + 7 <8, inégalité incorrecte, alors cet élément de table sera 0
1 + 8 <8, encore 0
3
Pour connaître le nombre d'arêtes, comptez le nombre d'unités dans la matrice d'adjacence, sans déchirer les arêtes.
Dans l'exemple, une matrice symétrique a été obtenue, par conséquent, les unités ont d'abord été calculées au-dessus de la diagonale principale de la matrice (marquée en bleu), puis les unités sur la diagonale principale (marquée en rouge). Le nombre total de côtes est de 12.
4
Construisez une matrice d'incidents (contours). 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 les unités dans les lignes qui seront connectées par un bord. Les bords menant du haut à celui-ci sont appelés boucles et ajoutés à la fin de la matrice. Dans les colonnes correspondant aux boucles, il n'y a qu'une seule unité, contrairement aux autres bords.
5
Dessinez maintenant un graphique. Disposez les sommets sur du papier de manière arbitraire et connectez-les avec les bords à l'aide des tableaux construits. Les sommets non reliés par des arêtes sont appelés isolés.
Faites attention
La figure montre les côtes pour plus de clarté. Habituellement, le poids de la côte est inscrit sur la côte.
