Please enable JavaScript.
Coggle requires JavaScript to display documents.
Teoría de Grafos - Coggle Diagram
Teoría de Grafos
¿Qué es un grafo?
Un grafo es una estructura compuesta por un conjunto de vértices, aristas y en base a estas últimas, una función de incidencia, que define a qué vértices se dirige la arista.
Vértices
Adyacente
Es aquel que se vincula con el vértice V a través de las distintas aristas, por ejemplo, si A1 se conecta con V1 y V2, el vértice adyacente de V1 sería V2.
Grado o Valencia
Es una función que nos devuelve la cantidad de aristas incidentes en el vértice especificado, en este caso los bucles se cuentan al doble.
-
Aislado
Es aquel que no es adyacente a ningún otro vértice, que no está conectado por aristas.
-
Aristas
Incidentes
Aquellas aristas que se unen en un vértice especificado, por ejemplo, si se indica V2, se tomarán en cuenta todas las aristas que tengan dicho vértice como extremo.
Representación Matricial
Matriz de Adyacencia
Es una matriz cuadrada en la que las filas y columnas representan vértices que al evaluar, sus valores pueden ser 1 si son adyacentes o 0 en caso de no serlo, también se le conoce como matriz booleana de n*n
Matriz de Incidencia
Es una matriz rectangular, en la que las filas representan vértices y las columnas aristas, puede ser 1 si el vértice es extremo de la arista y 0 en caso de no serlo, se identifica como matriz booleana n*m
Adyacentes
Aquellas aristas que tienen sólo un vértice en común, si A1 y A2 se conectan respectivamente a {V1, V3} y {V1, V2}, en ese caso serían adyacentes.
-
Paralelas
Las aristas que comparten la misma función de incidencia, es decir, se conectan a los mismos vértices.
-
-
-
-