17208055
Description
Mind Map by Victor Leopoldo Maya, updated more than 1 year ago
|
Created by Victor Leopoldo Maya
almost 6 years ago
|
|
Conceptos
básicos de la
Teoría de
gráficas y las
Relaciones.
- Gráfica
(grafo)
- Un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas), permiten estudiar
las interrelaciones entre unidades que interactúan unas con otras.
- Por ejemplo, una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices
representan terminales y las aristas representan.
- Un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas), permiten estudiar
las interrelaciones entre unidades que interactúan unas con otras.
- Vértice
(nodo)
- Es la unidad fundamental de la que
están formados los grafos.
- Un grafo no dirigido está formado por un conjunto de vértices y un
conjunto de aristas (pares no ordenados de vértices)
- Un grafo no dirigido está formado por un conjunto de vértices y un
conjunto de aristas (pares no ordenados de vértices)
- Es la unidad fundamental de la que
están formados los grafos.
- Arista
(arco)
- En teoría de grafos, una arista corresponde a una relación entre
dos vértices de un grafo.
- Para caracterizar un grafo G son suficientes únicamente el conjunto de todas sus aristas, comúnmente denotado
con la letra E (del término en inglés edge), junto con el conjunto de sus vértices, denotado por V.
- Así, dicho grafo se puede como G(V,E), o bien G = (V,E).
- En teoría de grafos, una arista corresponde a una relación entre
dos vértices de un grafo.
- Vértices adyacentes
- Son aquellos que conforman un lado o arista.
- Todo lado conformado por dos vértices se dice que es incidente sobre esos vértices. Si un
vértice no tiene otro adyacente se dice que es aislado.
- Son aquellos que conforman un lado o arista.
- Bucle
- En un grafo es una arista
que conecta al mismo
vértice consigo mismo
- En un grafo es una arista
que conecta al mismo
vértice consigo mismo
- Matriz de adyacencia
- Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.
- Se trata de una matriz cuadrada de n filas \times n columnas (siendo n el número de vértices del grafo). Para construir la matriz de adyacencia, cada elemento
a_{ij} vale {{1}} cuando haya una arista que una los vértices i y j.
- En caso contrario el elemento a_{ij} vale 0. La matriz de adyacencia, por tanto, estará formada por ceros y unos.
- En caso contrario el elemento a_{ij} vale 0. La matriz de adyacencia, por tanto, estará formada por ceros y unos.
- Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.
- Matriz de incidencia
- Dado un grafo simple G = (V, E) con n=|V| vértices {v1,. .. , vn} y m=|E| aristas {e1, …, em}, su matriz de
incidencia es la matriz B de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.
- Si la matriz de incidencia sólo contiene ceros y unos
(matriz binaria). Como cada arista incide exactamente en
dos vértices, cada columna tiene exactamente dos unos.
La cantidad de unos que aparece en cada fila es igual al
grado del vértice correspondiente. Una fila compuesta
sólo por ceros corresponde a un vértice aislado.
- Si la matriz de incidencia sólo contiene ceros y unos
(matriz binaria). Como cada arista incide exactamente en
dos vértices, cada columna tiene exactamente dos unos.
La cantidad de unos que aparece en cada fila es igual al
grado del vértice correspondiente. Una fila compuesta
sólo por ceros corresponde a un vértice aislado.
- Dado un grafo simple G = (V, E) con n=|V| vértices {v1,. .. , vn} y m=|E| aristas {e1, …, em}, su matriz de
incidencia es la matriz B de orden nxm, B(G)=(bij), donde bij=1 si vi es incidente con ej y bij=0 en caso contrario.
- Grado de un vértice
- Se llama grado de un vértice v al número de aristas que lo tienen como extremo, (cada bucle lo cuenta dos veces). Se designa por d(v) y corresponde al número de aristas incidentes sobre el vértice v. Un vértice
aislado tiene grado cero. En los grafos dirigidos el grado total de un vértice es la suma del grado entrante más el grado saliente. En los grafos no dirigidos, el grado total de un vértice es igual al número de aristas que
tiene el vértice. Por lo tanto, la suma de los grados de los vértices es igual al doble de las aristas del grafo.
- Se llama grado de un vértice v al número de aristas que lo tienen como extremo, (cada bucle lo cuenta dos veces). Se designa por d(v) y corresponde al número de aristas incidentes sobre el vértice v. Un vértice
aislado tiene grado cero. En los grafos dirigidos el grado total de un vértice es la suma del grado entrante más el grado saliente. En los grafos no dirigidos, el grado total de un vértice es igual al número de aristas que
tiene el vértice. Por lo tanto, la suma de los grados de los vértices es igual al doble de las aristas del grafo.
- Grafo simple
- Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista
- Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista
- Multígrafo
- Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que
relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista.
Formalmente, un multigrafo G es un par G:=(V, E) donde: V es un conjunto de vértices o nodos.
- Un multigrafo o pseudografo es un grafo que está facultado para tener aristas múltiples; es decir, aristas que
relacionan los mismos nodos. De esta forma, dos nodos pueden estar conectados por más de una arista.
Formalmente, un multigrafo G es un par G:=(V, E) donde: V es un conjunto de vértices o nodos.
- Dígrafo (digráfica)
- es un tipo de grafo en el cual las aristas tienen un sentido definido, a diferencia del grafo no dirigido, en el cual
las aristas son relaciones simétricas y no apuntan en ningún sentido.
- es un tipo de grafo en el cual las aristas tienen un sentido definido, a diferencia del grafo no dirigido, en el cual
las aristas son relaciones simétricas y no apuntan en ningún sentido.
- Camino
- Trayectoria o camino Corresponde a los vértices por los cuales hay que pasar para ir desde un vértice w hacia
un vértice v. Es decir un camino entre dos vértices es una lista de vértices que están conectados por una arista
del grafo
- Para que un camino o trayectoria exista es condición necesaria que las
aristas sobre la trayectoria existan sobre el conjunto de aristas que
definen el grafo.
- Para que un camino o trayectoria exista es condición necesaria que las
aristas sobre la trayectoria existan sobre el conjunto de aristas que
definen el grafo.
- Trayectoria o camino Corresponde a los vértices por los cuales hay que pasar para ir desde un vértice w hacia
un vértice v. Es decir un camino entre dos vértices es una lista de vértices que están conectados por una arista
del grafo
- Ciclo (circuito)
- Un ciclo (también llamado circuito) es un camino simple de longitud mínimo 1 que empieza y termina en el
mismo vértice; es decir, es una trayectoria simple en la cual el primero y el último vértices son el mismo.
- Un ciclo (también llamado circuito) es un camino simple de longitud mínimo 1 que empieza y termina en el
mismo vértice; es decir, es una trayectoria simple en la cual el primero y el último vértices son el mismo.
- Camino/ciclo euleriano
- Un camino euleriano es un camino que pasa por cada arista una y solo una vez.
- Un camino euleriano es un camino que pasa por cada arista una y solo una vez.
- Un ciclo o circuito euleriano
- es un camino cerrado que recorre cada arista exactamente una vez
- es un camino cerrado que recorre cada arista exactamente una vez
- Camino/ciclo hamiltoniano
- Un camino hamiltoniano es un camino que pasa
por cada vértice exactamente una vez. Un grafo
que contiene un camino hamiltoniano se
denomina un ciclo hamiltoniano si es un ciclo
que pasa por cada vértice exactamente una vez
(excepto el vértice del que parte y al cual llega).
Un grafo que contiene un ciclo hamiltoniano se
dice grafo hamiltoniano. Estos conceptos se
pueden extender para los grafos dirigidos los
cuales son igual a un carro.
- Un camino hamiltoniano es un camino que pasa
por cada vértice exactamente una vez. Un grafo
que contiene un camino hamiltoniano se
denomina un ciclo hamiltoniano si es un ciclo
que pasa por cada vértice exactamente una vez
(excepto el vértice del que parte y al cual llega).
Un grafo que contiene un ciclo hamiltoniano se
dice grafo hamiltoniano. Estos conceptos se
pueden extender para los grafos dirigidos los
cuales son igual a un carro.
- Árbol
- Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Sea G =(V,A) un grafo
no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un
vértice particular designado como raíz.
- Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Sea G =(V,A) un grafo
no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un
vértice particular designado como raíz.
- Árbol de expansión
- En teoría de grafos,
un árbol de
expansión, árbol
generador o árbol
recubridor T de un
grafo conexo, no
dirigido G es un
árbol compuesto
por todos los
vértices y algunas
de las aristas de G.
Informalmente, un
árbol de expansión
de G es una
selección de aristas
de G que forman
un árbol que cubre
todos los vértices.
- En teoría de grafos,
un árbol de
expansión, árbol
generador o árbol
recubridor T de un
grafo conexo, no
dirigido G es un
árbol compuesto
por todos los
vértices y algunas
de las aristas de G.
Informalmente, un
árbol de expansión
de G es una
selección de aristas
de G que forman
un árbol que cubre
todos los vértices.
- Relación binaria
- En matemáticas, una relación binaria es una relación matemática definida entre los elementos de dos
conjuntos y. Una relación de en se puede representar mediante pares ordenados
- En matemáticas, una relación binaria es una relación matemática definida entre los elementos de dos
conjuntos y. Una relación de en se puede representar mediante pares ordenados
- Digráfica de una relación
- Es una gráfica que nos sirve para representar relaciones mediante puntos o vértices, lineas o lazos
- Es una gráfica que nos sirve para representar relaciones mediante puntos o vértices, lineas o lazos
- Matriz de una relación
- es una manera conveniente de representar una relación R de X a Y
- es una manera conveniente de representar una relación R de X a Y
- Propiedades de una relación: reflexiva, simétrica, transitiva, antisimétrica
- La relación R es reflexiva si y sólo si A tiene 1 en la diagonal principal
- La relación R es reflexiva si y sólo si A tiene 1 en la diagonal principal
- Relación de equivalencia
- Sea R una relación de equivalencia en un conjunto X. Para cada a ∈ X. sea (En palabras, [a] es el conjunto de
todos los elementos de X que están relacionados con a). Entonces S = {[a] |a ∈ X} es una partición de X.
- Sea R una relación de equivalencia en un conjunto X. Para cada a ∈ X. sea (En palabras, [a] es el conjunto de
todos los elementos de X que están relacionados con a). Entonces S = {[a] |a ∈ X} es una partición de X.
- Cerradura transitiva de una relación
- La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo
transitiva contiene al conjunto de pares de la relación binaria original. La clausura transitiva de una relación
{\displaystyle R\,} R\, se denotada {\displaystyle CT(R)\,} {\displaystyle CT(R)\,}
- La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo
transitiva contiene al conjunto de pares de la relación binaria original. La clausura transitiva de una relación
{\displaystyle R\,} R\, se denotada {\displaystyle CT(R)\,} {\displaystyle CT(R)\,}
Want to create your own Mind Maps for free with GoConqr? Learn more.