El gráfico consta de vértices y aristas. Los vértices están conectados por aristas de acuerdo con una determinada propiedad: la relación de incidencia, que define el conjunto de aristas. En este caso, se pueden formar bucles y vértices aislados.
Manual de instrucciones
1
Deje que se proporcione un conjunto de bordes de un gráfico y una relación dada por la cual se puede dibujar un borde de un vértice a otro. Como ejemplo, el conjunto de vértices {1, 2, 3, 4, 5, 6, 7, 8}, los dos vértices x e y están en la relación x + y <8.
2
Construye una matriz de adyacencia de vértice. Para hacer esto, construya una tabla cuadrada, el número de filas y columnas en la tabla coincide con el número de vértices. Luego ponga 1 en la intersección de la fila i-ésima y la columna j-ésima, si los vértices i y j satisfacen la proporción dada. Ponga 0 en la intersección de la fila i-ésima y la columna j-ésima, si no se satisface la razón para los elementos correspondientes.
En nuestro ejemplo, la primera línea se llena de la siguiente manera:
1 + 1 <8, entonces en la intersección de la 1ra fila y la 1ra columna es 1
1 + 2 <8, nuevamente 1
1 + 3 <8, nuevamente 1
…
1 + 7 <8, desigualdad incorrecta, entonces este elemento de tabla será 0
1 + 8 <8, nuevamente 0
3
Para averiguar la cantidad de aristas, cuente la cantidad de unidades en la matriz de adyacencia, sin rasgar las aristas.
En el ejemplo, se obtuvo una matriz simétrica, por lo tanto, primero las unidades se calcularon por encima de la diagonal principal de la matriz (marcada en azul), y luego las unidades en la diagonal principal (marcada en rojo). El número total de costillas es 12.
4 4
Construya una matriz de incidentes (bordes). Para hacer esto, dibuje una tabla, el número de filas es igual al número de vértices del gráfico y el número de columnas al número de bordes. Coloque las unidades en las líneas que estarán conectadas por un borde. Los bordes que van desde la parte superior se denominan bucles y se agregan al final de la matriz. En las columnas correspondientes a los bucles, solo hay una unidad, a diferencia de los otros bordes.
5 5
Ahora dibuja un gráfico. Organice los vértices en papel arbitrariamente y conéctelos con los bordes utilizando las tablas construidas. Los vértices no conectados por bordes se denominan aislados.
Presta atencion
La figura muestra las costillas para mayor claridad. Por lo general, el peso de la costilla se escribe sobre la costilla.
