Matrices de Adyacencia en Grafos Dirigidos

Clase 23 de 40 • Curso de Matemáticas Discretas

Resumen

Para saber a partir de nuestra matriz si nuestro grafo es dirigido o no dirigido basta con analizar si la matriz es simétrica o asimétrica, en caso de ser simétrica entonces el grafo es no dirigido y si es asimétrica entonces el grafo es dirigido.

Luis Fernando Úbeda Camacho

student•

Apuntes de clase

Grafo dirigido = matriz asimétrica
Grafo no dirigido = matriz simétrica
En la matriz de adyacencia asimétrica, si sumamos las filas de cada nodo nos dirá la cantidad de conexiones que inciden en el nodo, y si miramos las columna nos dirá sobre que nodo inciden los nodos.

Sergio Orduz

teacher•

Genial @luifer088 cuéntame como te termino de ir con el curso cuales estas tomando ahora

Maria Guadalupe Diaz Escobar

student•

Gracias por el resumen

Rodrigo Urquizo Yepez

student•

En una matriz de adyacencia para un grafo no dirigido si cambiamos las columnas por filas o viceversa nos debe dar la misma matriz, es decir, debe ser una matriz simetrica, ya que estamos hablando de conexiones sin importar la direccion, esto en pocas palabras es como decir, si tenemos en la casilla a y b un 1, en la casilla b y a tambien debe ser 1. Por el contrario en un grafo dirigido esto no necesariamente va a ser lo mismo, por lo que nuestra matriz puede ser tanto simetrica como no simetrica, las conexiones pueden estar dirigidas solo hacia un nodo o dirigidas hacia ambos nodos.

Edwin Ernesto Menjivar Ramirez

student•

Gracias por el aporte!

Maria Guadalupe Diaz Escobar

student•

Gracias por el aporte

Julián Avella

student•

Le falto decir que los vértices de la columna son los que reciben una arista y los vértices de la fila son de los que parte una arista .)

Jordi Santamaría Portolés

student•

Basicamente, si hay una conexion a con b, pero no hay una b con a, el grafo ya es dirigido, ya que al no haber conexion en ambos lados, solo hay una direccion.

Josue Noha Valdivia

student•

Notas

Matriz de adyacencia simétrica → grafo no dirigido
Matriz de adyacencia asimétrica → grafo dirigido

Luis Arturo Huerta Rodríguez

student•

Miguel Andres Rendon Reyes

student•

En los grafos simples, se tiene en cuenta, de que nuestro grafo cumple la ley conmutativa, mientras que el grafo dirigido no. Podrìamos asimilar un grafo simple como una suma o multiplicaciòn, dònde el orden los factores (en este caso nodos) no afecta el resultado, mientras que en un grafo dirigido es como una resta o divisiòn, dònde el orden de los factores, altera por mucho el resultado.

Miguel Andres Rendon Reyes

student•

Recordar que en el nùmero de filas, se encuentran el nùmero de nodos, tanto en la matriz de adyacencia como en la matriz de incidencia.

Max Andy Diaz Neyra

student•

Matriz Adyacencia 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 el nodo tiene una conexión en bucle y el grafo es no dirigido asignamos 2. Si es dirigido le asignamos 1. Se suman las contribuciones y se asigna el resultado.

Nota: • En caso de ser el grafo no dirigido la matriz será simétrica y al sumar cada fila o columna nos dará el grado de cada vértice • 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 .

Julián Avella

student•

Una matriz es simétrica, cuando es cuadrada, la cual tiene la característica de ser igual en su lado opuesto y una matriz asimétrica no tiene su lado igual

Jhins Ledys Cárdenas Pardo

student•

Excelente aplicación por medio del ejemplo.

Cesar Eduardo Montoya Santiago

student•

Buena representacion y ejemplo

Maximiliano A. Almeira

student•

La interacción entre C y D no se podría representar con un solo camino bidireccional? O es necesario colocar dos caminos con distintos sentidos?

Carlos Daniel Pimentel Díaz

student•

Hola Maximiliano. Podrías hacerlo. Como dice el adagio popular: "el papel aguanta todo". Pero por convención es mejor conectar esos nodos con flechas dirigidas diferentes. ¿Porqué? Porque en Teoría de Grafos, se supone que no puedes ir por esa conexión en sentido contrario. Imagínalo como una calle en un solo sentido, donde es prohibido ir en sentido contrario a la dirección establecida.

Leandro Tenjo

student•

El profesor dijo:

“Si fuera una conexión bidirectional, veríamos un 2 en algún lugar de la table. Como es un Grafo dirigido, cada arista tiene su propio camino”

Pavel Fernando Montalvan Giron

student•

Porque en la matriz de c-d no figura el numero 2 ?

Milton Martinez

student•

porque es un grafo dirigido, entonces va cada dirección en cada elemento de la matriz.

Virna Fiorella Jiménez Lanza

student•

¿Podría representarse por ejemplo la conexión de c y d con solo una arista pero con dos direcciones?

Leandro Tenjo

student•

El profesor dijo:

“Si fuera una conexión bidirectional, veríamos un 2 en algún lugar de la table. Como es un Grafo dirigido, cada arista tiene su propio camino”

Martín Valverde

student•

En la matriz de adyacencia asimétrica dibujamos cada una de las conexiones dirigidas. Si representamos anteriormente C con D, y tenemos otra conexión D con C, debemos dibujar ambas de manera dirigida.

Daniel Millaqueo Fuentes

student•

Excelente :)

Raul Armas

student•

Bien!

Wilson Fernando Antury Torres

student•

Cuando la matriz es no simétrica decimos que es un grafo dirigido.

Alex Fernández

student•

Excelente clase.

Matrices de Adyacencia en Grafos Dirigidos

Introducción al curso

Matemáticas Discretas: Lógica, Conjuntos y Teoría de Gráficas

Lógica

Lógica Proposicional: Conceptos y Aplicaciones Básicas

Tablas de verdad y conectores lógicos: conjunción, disyunción y más

Construcción de Tablas de Verdad para Proposiciones Compuestas

Construcción de Tablas de Verdad para Proposiciones Lógicas

Tablas de Verdad y Análisis de Proposiciones Lógicas

Circuitos Lógicos: Representación y Función en Electrónica

Circuitos Lógicos para Proposiciones Compuestas

Tablas y Circuitos Lógicos: Ejercicios Prácticos

Teoría de conjuntos

Conjuntos: Definición, Pertenencia y Representación Matemática

Conjuntos: Nulo, Unitario y Universal y Operaciones Básicas

Representación Gráfica de Operaciones entre Conjuntos

Propiedades de los Conjuntos: Leyes de De Morgan y Representación Gráfica

Representación gráfica de las leyes de De Morgan

Operaciones y Propiedades de Conjuntos: Ejercicio Práctico Resuelto

Operaciones Básicas con Conjuntos y Problemas de Conjuntos

Teoría de grafos

Teoría de Gráficas: Conceptos y Aplicaciones Prácticas

Grado de Vértices y Conexiones en Gráficas Simples

Caminos y ciclos eulerianos en grafos: teoría y aplicación

Caminos y Ciclos Hamiltonianos en Grafos

Construcción de Matrices de Adyacencia para Representar Grafos

Representación de Grafos con Matriz de Incidencia

Matrices de Adyacencia en Grafos Dirigidos

Análisis de Caminos y Ciclos Eulerianos en Grafos

Árboles

Árboles y Tipos de Árboles en Matemáticas Discretas

Estructuras de Árboles en Programación y Jerarquías de Datos

Conceptos Básicos de Estructuras de Árboles en Informática

Árbol de Expansión Mínima: Conexión Óptima de Nodos

Tipos de Árboles Binarios y sus Características

Recorridos de Árboles: Preorden, Inorden y Posorden

Árboles Binarios para Expresiones Aritméticas

Transformación de Expresiones Aritméticas en Árboles Binarios

Árboles: Altura, Niveles y Recorridos Ordenados

Algoritmos

Algoritmo de Prim: Árbol de Expansión Mínimo en Grafos

Algoritmo de Dijkstra: Ruta Óptima y Coste Mínimo

Algoritmo de Kruskal

Algoritmo de Flury: Encontrar Ciclos Eulerianos en Grafos

Algoritmo de Flujo Máximo en Redes Dirigidas

Algoritmos de Grafos: Prim, Dijkstra, Kruskal y Fleury

Conclusiones

Repaso Final de Matemáticas Discretas: Lógica, Conjuntos y Algoritmos