Existen diferentes formas de representar un grafo, ya hemos visto su representación gráfica, en esta clase vamos a ver como se representan con una matriz.
Dentro de la matriz vamos a representar cada fila y columna con un nodo, si existe una conexión entre dos nodos entonces colocaremos un uno en la celda correspondiente, si no existe una conexión colocaremos un cero. Si algún nodo tiene una conexión consigo mismo entonces colocaremos un 2.
Al sumar todas las filas nos dará como resultado el grado de cada vértice.
La matriz de adyacencia es una de las representaciones más utilizadas.
Curso de Matemáticas Discretas
Clase 21 / 40
Curso de Matemáticas Discretas
Clase 21 / 40
Existen diferentes formas de representar un grafo, ya hemos visto su representación gráfica, en esta clase vamos a ver como se representan con una matriz.
Dentro de la matriz vamos a representar cada fila y columna con un nodo, si existe una conexión entre dos nodos entonces colocaremos un uno en la celda correspondiente, si no existe una conexión colocaremos un cero. Si algún nodo tiene una conexión consigo mismo entonces colocaremos un 2.
Al sumar todas las filas nos dará como resultado el grado de cada vértice.
La matriz de adyacencia es una de las representaciones más utilizadas.
Me parece que hay en un error:
El grado de un vértice es el numero de aristas que tienen a ese vértice como extremo. Una gráfica puede contener una arista de un vértice a si mismo; tal arista es un bucle cerrado (o lazo).Un bucle cerrado contribuye en 2 unidades al grado de un vértice.
Para mas información recomiendo: Estructuras de Matemáticas Discretas para la Computación de Kolman, Busby, Ross.
Hay confucion con la notacion que se debe colocar cuando existe un pseudografo. En el siguinte video https://www.youtube.com/watch?v=cNAkUZaiDo4 mencionan que se coloca un 1 cuando pasa y se le llama bucle. Sin embargo, en el libro de Matematicas Discretas de Richard Johnsonbaugh menciona todo lo contrario, como acá se muestra: 
Es muy importante que el equipo de Platzi y el mismo @sdorduzc nos lo aclare. Muchas gracias.
Vamos a calmarnos!, estuve investigando y en la quinta edición del libro de Matemática Discreta y sus aplicaciones de Rosen, en la página 523, menciona que en el caso de un pseudografo se debe colocar un 1 en la matriz de adyacencia. Igualmente la librería networkx de Python asume este valor por default para la matriz de adyacencia cuando un nodo está conectado con sí mismo siempre y cuando no se le asigne un peso. The convention used for self-loop edges in graphs is to assign the diagonal matrix entry value to the edge weight attribute (or the number 1 if the edge has no weight attribute).
Parece que aquí hay una controversia. En este video de la universidad politécnica de valencia, realizan el procedimiento como en esta clase, asignan 1 al nodo con conexión consigo mismo. Dan una explicación matemática convincente.
Matriz de adyaciencia, para ver el grado de cada vertice, es verificable, y se puede del grafo ir a la matriz y de la matriz al grafo,
Me parece que hay confusion con el tema de la arista que que se comporta como pseudografo. Consulté en videos como https://www.youtube.com/watch?v=cNAkUZaiDo4 que cuando una arista sale de un nodo y llega al mismo nodo, su valor es de 1 y se interpreta como un bucle. Sin embargo, en el libro de Matemáticas Discretas de Richard Johnsonbaugh 6 Ed. dice todo lo contrario, como lo muetra aqui:
Por favor, nos pueden aclarar este tema?. Gracias
Apuntes de clase
Matriz de adyacencia
Solo para dar mi aporte De acuerdo con el Libro de Matemáticas para la Computación de José Alfredo Jiménez Murillo y de la Universidad Politécnica de Valencia y Universidad Católica de Murcia La Matriz de Adyacencia solo contiene 1 y 0. El bucle se representa como 1. Esto es debido a que la matriz de adyacencia solo representa relaciones El grado se obtiene con la matriz de incidencia
Matriz de adyacencia Definición: Es la forma de presentar un grafo de n nodos mediante una matriz nxn donde cada fila y columna representa un nodo. Pasos para asignar valores a la celda correspondiente:
Si existe una conexión entre dos nodos entonces asignamos un uno. Se suman las contribuciones de las conexiones y se asigna el resultado
Si no existe una conexión colocaremos un cero
Si algún nodo tiene una conexión consigo mismo entonces asignamos un 2. Se suman las contribuciones y se asigna el resultado
Nota:
En caso de ser el grafo no dirigido la matriz sera simetrica y al sumar cada fila o columna nos dara el grado de cada verticie
En caso de ser el grafo dirigido, si sumamos las columnas obtenemos el grado de entrada y si sumamos las filas el grado de salida .
