Matriz de adyacencia

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.

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 .

Hay varias formas de representar los graficos, pero si un grafico es complejo se puede recorrer en una matriz de adyacencia.
Esta matriz se construye con una tabla de nxn (igual numero de filas y columnas) que van a representar los nodos, se analizan las conexiones de cada una ( si es un pseudografico = 1, simple = 1, multigrafo = 2, digido = 1 (dependiendo de la direccion) o si no hay conexion = 0) y el grado se determina con la sumatoria de cada fila.

Sería bueno que alguien del Team Platzi aclare este asunto de los pseudografos. Particularmente, me parece que para un nodo que tiene conexión consigo mismo basta con colocar un 1 igual que como pasa con la conexión entre 2 nodos diferentes. Un 2 da a entender que hay 2 conexiones en el mismo nodo, y en el primer ejemplo este no es el caso

En la descripción del video lo corrige “Si algún nodo tiene una conexión consigo mismo entonces colocaremos un 2”. No le den mas vuelta, deberían corregir esa parte porque hace que surjan dudas innecesarias.

buenas, una pregunta: ¿se representa en la matriz igual si el grafo es dirigido?
gracias

Matriz de Adyacencia:
Es la representación de un grafo a través de sus nodos y sus conexiones. Se genera mediante una tabla de doble entrada donde cada entrada representa un vértice en el que las casillas representan el número de caminos que hay entre los vertices.
Nota:
La suma de las filas equivale al grado de su respectivo vértice

Mis apuntes:
https://www.remnote.io/a/matriz-de-adyacencia-/6393a64250c0f94085a3b1f4

Nótese que hay información duplicada en esas tablas. No nos importa si el enlace es de A a B o de B a A, por lo que podríamos ahorrar la mitad de la memoria.

Con esto también podemos representar grafos dirigidos. Serían aquéllos cuyos valores de X a Y sean distintos que de Y a X

Notas:

Matriz de Adyacencia
Analizar nodo por nodo para ver las connexiones entre si.

Si sumamos los resultados de cada una de las filas, nos da como resultado los grados de cada nodo.

Una forma eficiente de representar gráficas complejas, son las matrices de adyacencia, en las que ponemos en las filas, los nodos en orden y también en las columnas, lo leemos así: En la columna, empezamos por a, luego en la fila, empezamos también con a, y preguntamos ¿Hay conexión entre a y a? si la respuesta es afirmativa, entonces agregamos el 2, debido a digamos que en este ejemplo a tiene solo una conexión en si mismo y eso hace que los dos extremos de la arista lleguen al mismo nodo. Luego seguimos con el siguiente elemento en la fila, que sería el b, luego hacemos la misma pregunta, en caso de que no, entonces ponemos un 0. En caso de que existan más de una arista, entonces ponemos ese número.

• Representar un grafo en forma de 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 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 nodo.

• La matriz de adyacencia es una de las representaciones más utilizadas.

Cuando en un nodo tiene 2 o mas caminos hacia si mismo (pseudografo). Tienen que estar representados estos camino uno dentro de otro o pueden estar fuera siempre y cuando se conecten al mismo nodo?

… También la suma de sus columnas es igual al grado…
… Me di cuenta que la matriz de adyacencia y su transpuesta son iguales…
… Me imagino que por la propia naturaleza de la matriz…

¿Existe algún teorema?, ¿es así siempre?

Excelente explicación y super claro el contenido!

Buenas, tenia entendido que al tener un vertice conectado con si mismo, el grado de este aumenta en 2.
En otras palabras el grado del vertice a del primer ejercicio deberia ser 4. Y en el segundo ejercico, el vertice a el grado es 4, el vertice b el grado 5, y el vertice c el grado 5.

Buena clase.

Gran clase.

Para un grafo con |V|∣V∣vertical bar, V, vertical bar vértices, una matriz de adyacencia es una matriz de |V| \times |V|∣V∣×∣V∣vertical bar, V, vertical bar, times, vertical bar, V, vertical bar de ceros y unos, donde la entrada en el renglón iii y la columna jjj es 1 si y solo si la arista (i, j)(i,j)left parenthesis, i, comma, j, right parenthesis está en el grafo. Si quieres indicar un peso de la arista, ponlo en la entrada del renglón iii, columna jjj y reserva un valor especial (tal vez null) para indicar una arista ausente.

Por ejemplo:

Que en JavaScript se vería de la siguiente manera:

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

Excelente, super claro todo el contenido!

De hecho en la descripción del video dice que si un nodo conecta con sigo mismo se pone en número 2.

Interesante tema

lógica espacio-temporal básica, gracias grafos

¿No debería ser 2, en el caso de A con si mismo, ya que se trata de un pseudografo?
Muchas gracias