No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Matriz de adyacencia

21/40
Recursos

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.

Aportes 31

Preguntas 4

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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 .

En la descripci贸n del video lo corrige 鈥淪i 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

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

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|鈭鈭ertical bar, V, vertical bar v茅rtices, una matriz de adyacencia es una matriz de |V| \times |V|鈭鈭C椻垼V鈭ertical 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