Conceptos básicos de la Teoría de gráficas y las Relaciones.

Gráfica (grafo)
1. 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.
2. 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.
Vértice (nodo)
1. Es la unidad fundamental de la que están formados los grafos.
  1. Un grafo no dirigido está formado por un conjunto de vértices y un conjunto de aristas (pares no ordenados de vértices)
Arista (arco)
1. En teoría de grafos, una arista corresponde a una relación entre dos vértices de un grafo.
2. 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.
3. Así, dicho grafo se puede como G(V,E), o bien G = (V,E).
Vértices adyacentes
1. Son aquellos que conforman un lado o arista.
2. 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.
Bucle
1. En un grafo es una arista que conecta al mismo vértice consigo mismo
Matriz de adyacencia
1. Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.
2. 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.
  1. En caso contrario el elemento a_{ij} vale 0. La matriz de adyacencia, por tanto, estará formada por ceros y unos.
Matriz de incidencia
1. 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.
  1. 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.
Grado de un vértice
1. 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
1. Un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista
Multígrafo
1. 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)
1. 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
1. 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
  1. 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.
Ciclo (circuito)
1. 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
1. Un camino euleriano es un camino que pasa por cada arista una y solo una vez.
Un ciclo o circuito euleriano
1. es un camino cerrado que recorre cada arista exactamente una vez
Camino/ciclo hamiltoniano
1. 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
1. 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
1. 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
1. 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
1. Es una gráfica que nos sirve para representar relaciones mediante puntos o vértices, lineas o lazos
Matriz de una relación
1. 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
1. La relación R es reflexiva si y sólo si A tiene 1 en la diagonal principal
Relación de equivalencia
1. 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
1. 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)\,}

Siguiente

Conceptos básicos de la Teoría de gráficas y las Relaciones.

Descripción

Resumen del Recurso

Similar

	Creado por Victor Leopoldo Maya hace casi 6 años