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.
Instrucciones
Paso 1
Supongamos que se da el conjunto de aristas del gráfico y se da la relación a lo largo de la cual es posible trazar una arista de un vértice a otro. Como ejemplo, el conjunto de vértices {1, 2, 3, 4, 5, 6, 7, 8}, dos vértices xey están en la razón x + y <8.
Paso 2
Construya una matriz de adyacencia de vértices. 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 i-ésima fila y la j-ésima columna si los vértices i y j satisfacen la razón dada. Ponga 0 en la intersección de la i-ésima fila y la j-ésima columna si no se cumple la razón de los elementos correspondientes.
En nuestro ejemplo, la primera línea se completa de la siguiente manera:
1 + 1 <8, por lo que hay 1 en la intersección de la primera fila y la primera columna
1 + 2 <8, nuevamente 1
1 + 3 <8, nuevamente 1
1 + 7 <8, desigualdad incorrecta, por lo que este elemento de la tabla será 0
1 + 8 <8, nuevamente 0
Paso 3
Para averiguar el número de aristas, cuente el número de unos en la matriz de adyacencia sin duplicar las aristas.
En el ejemplo, se obtuvo una matriz simétrica, por lo que contamos primero las que están arriba de la diagonal principal de la matriz (marcadas en azul), y luego las de la diagonal principal (marcadas en rojo). El número total de costillas es 12.
Paso 4
Construye una matriz de incidentes (bordes). Para hacer esto, dibuje una tabla, el número de filas en ella es igual al número de vértices en el gráfico y el número de columnas es igual al número de aristas. Coloque unidades en esas líneas que estarán conectadas por un borde. Los bordes que van desde el vértice hasta él se denominan bucles y se agregan al final de la matriz. En las columnas correspondientes a los bucles, solo hay una unidad, en contraste con el resto de aristas.
Paso 5
Ahora dibuja un gráfico. Coloque los vértices en el papel de cualquier manera y conéctelos con los bordes usando las tablas construidas. Los vértices que no están conectados por aristas se denominan aislados.
