Construcción de Matrices de Adyacencia para Representar Grafos

Clase 21 de 40 • Curso de Matemáticas Discretas

Resumen

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.

Irving Ariel Escamilla Jacobo

student•

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.

Nicolás Neira Navarrete

student•

Lo que comenta Irving es muy importante para el desarrollo conceptual de lo que se explica en esta clase... tocará escribir al team de @platzi para que corrobore y de ser el caso que baje el video o que hagan la modificación correspondiente

Carlos Perilla

student•

No creo que tengan que bajarlo, pero es bueno tomar en cuenta ese concepto. Para quien quiera saber más de grafos, le recomiendo esta lista de videos: https://www.youtube.com/watch?v=c46I-gK3wV0&list=PL6kQim6ljTJu44dsVeZifHHiuDC1MEZ7q&index=7 "Teoría de grafos para la vida real" Son muy instructivos!

Jhins Ledys Cárdenas Pardo

student•

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.

Javier Marcelo Marchán Ordinola

student•

lo que pasa es que si te fijas si estas contando 2 veces, osea cuentas la conexión de AC y la conexión de CA, por lo tanto de uno mismo seria de ida y vuelta, pero imaginate si fuera grafo dirigido, es decir de AC se puede ir pero no de CA

Percival Ernesto Amezola Rivera

student•

Hola a todos platzinautas. En la sección de recursos aclara este tema.

Alfonso Neil Jiménez

student•

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).

Percival Ernesto Amezola Rivera

student•

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.

JUAN CAMILO CAMPO TANGARIFE

student•

Exactoo!!

eduardo fletes

student•

Muchas gracias por el video con la explicación, me quedó claro. Aunque la profesora tiene cara como que no quería explicar jeje

Jose Rodriguez

student•

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,

Sergio Orduz

teacher•

¡Excelente aporte Barinet!

Jhins Ledys Cárdenas Pardo

student•

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

Luis Fernando Úbeda Camacho

student•

Apuntes de clase

Matriz de adyacencia

Para convertir nuestro grafo en una matriz de adyacencia, analizaremos las conexiones de cada nodo y las representaremos con la forma de una matriz, donde relacionamos los grados de los vértices de cada uno de ellos.
La suma de las filas de cada vértice nos dirá el total de grados que tiene el vértice
La matriz de adyacencia nos sirve para representar un grafo

Ray Trápala

student•

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

Percival Ernesto Amezola Rivera

student•

De acuerdo con tu aportación, encontré el video de la universidad politécnica de valencia https://youtu.be/cNAkUZaiDo4

Max Andy Diaz Neyra

student•

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 .

Sara Yaneth Contreras Elías

student•

james Cortes Valencia

student•

A un me quedo la confusión cuando existe un pseudografo cual es su notación en la matriz de adyacencia? Porque en los textos citados por los compa;eros, aclaran que se debe color un +2 cuando hay una conexión a si mismo. Seria bueno discutir sobre este punto.

Miguel Angel Luque Acevedo

student•

En la parte de recursos lo esclarece. Si se debe hacer uso de un +2. Una manera para ver esto es si recordamos que la sumatoria de todos los grados de un grafo da el doble de aristas. Si miramos la primera gráfica tenemos 7 aristas, pero al sumar los grados de los nodos no da 14. Si miramos el 2do la suma de los grados da 14, lo que implica un grafo con 7 aristas. Pero el grafo resultante tiene 9 aristas.

Oscar Bolaños

student•

"...si existe una conexión entre dos nodos entonces sumaremos un uno (+1) en la celda correspondiente, si no existe una conexión colocaremos un cero. Si algún nodo tiene una conexión consigo mismo entonces sumaremos un dos (+2)". Tal vez sea cosa mía pero creo que se entiende mejor así, además en el ejemplo de esta clase (Muy buena (Y) ) la celada (a,a) debería tener un tres. Si no es así, o el texto esta mal, estoy muy confundido (no tanto, pero no es congruente la descripción) ¡Aiuda!

Fabián Vega Alcota

student•

"si existe una conexión entre dos nodos entonces sumaremos un uno (+1) en la celda correspondiente, si no existe una conexión colocaremos un cero." A mí parecer hasta ahí está perfecto, no es necesario colocar un dos (+2). Como (a,a) existe, se coloca un 1, sino se colocaría un 0. No hay necesidad de sumar más aristas.

Oscar Bolaños

student•

Gracias, queda como una matriz boleana. Nice

Lucia Amparo Osorio Hernandez

student•

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.

VICTORIA HERNÁNDEZ MARTÍNEZ

student•

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

Lautaro Sebastián Alomar

student•

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.

Percival Ernesto Amezola Rivera

student•

Diego Acero

student•

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

Martin Calvento

student•

Si el grafo es dirigido la matriz no es simetrica, tiene otra forma, ya que no se puede ir y venir por la misma arista porque tiene una direccion definida

Jaime Andres Valencia Gaviria

student•

es casi igual , es solo tener en cuenta la dirección de la conexión

Josue Noha Valdivia

student•

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

Luis Angel Ramirez Temoxtle

student•

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

Erik Ucenik

student•

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