Please enable JavaScript.
Coggle requires JavaScript to display documents.
u1. Teorìa de grafos, Circuito de Euler. Un circuito de Euler es un…
u1. Teorìa de grafos
Grafo(Victor,V, E)
Definiciòn
Es un conjunto de nodos(vértices) y aristas
No dirigido
Conexo
Multigrafo
No cíclico
Elementos
Los elementos de un grafo son los siguientes:
-Aristas (Línea formada por la intersección de dos vértices).
-Vértices (Punto en el que coindicen 1 o más aristas).
-Caminos (Sucesión de vértices y aristas).
Clasificación.-
Grafo acíclico: Es aquel grafo no contiene ningún ciclo simple.
Grafo cíclico: Un grafo se dice cíclico si contiene algún ciclo simple.
Grafo denso: Un grafo denso es aquel grafo en el que el número de aristas está cercano al número de máximo de aristas.
Grafo dirigido: En los dirigidos, las aristas se recorren en un único sentido: desde el origen al destino de la flecha.
Grafo no dirigido: Son aquellos grafos en los cuales los lados no están orientados (no son flechas).
Grafo nulo: es el grafo cuyos conjuntos de aristas y de vértices son vacíos.
propiedades
Valencia/Grado: número de aristas relacionadas con el nodo
Tipo
Algoritmos de Bùsqueda( Pedro, Issac y Nahun) Conjunto de instrucciones que están diseñadas para localizar un elemento con ciertas propiedades dentro de una estructura de datos
ABB
Arbol de Expansión mínima
Por profundidad
Por amplitud
Algoritmo de Ruta màs corta (Tona, G, R)
Dijkstra
El algoritmo de Dijkstra es un algoritmo iterativo que nos proporciona la ruta más corta desde un nodo inicial particular a todos los otros nodos en el grafo.
Definición
El algoritmo de rutas más cortas es en uno de los módulos de análisis más importantes de los algoritmos de grafos Este se encarga de detectar dentro de un grafo cuál es la ruta más eficiente o el recorrido de menor distancia entre un par de vértices que conforman un grafo.
Floyd
El algoritmo de Floyd-Warshally, es un algoritmo de análisis sobre grafos para encontrar el camino mínimo en grafos dirigidos ponderados. El algoritmo encuentra el camino entre todos los pares de vértices en una única ejecución.
ârboles (Juan, Leopoldo, Fernanda)
DEFINICION
Estructura de datos de tipo abstracto, formado por nodos y ramas(líneas de unión de los nodos) imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados.
Tipos
ARBOL BINARIO
Estructura homogénea dinámica y no lineal en donde cada nodo le pueden seguir como máximo dos nodos hijos y cada hijo se designa según posición, hijo izquierdo o derecho.
BINARIO DISTINTO: aquel que su estructura es diferente a los otros árboles binarios.
BINARIO EQUIVALENTE: llamado así cuando su estructura e información de sus nodos es idéntica a otros árboles binarios
BINARIO EQUILIBRADO: todos sus nodos cumplen con la propiedad, dinámica y no lineal en donde el nodo puede seguir como máximo dos nodos hijos.
BINARIO LLENO: se le conoce así si el árbol binario de altura k que tiene 2^k-1
BINARIO COMPLETO: Si un árbol de altura k está completo si está lleno hasta la altura k-1 y los nodos del ultimo nivel están a la izquierda
BINARIO SIMILAR: su estructura es idéntica a la de otros árboles pero la información que guardan es diferente entre si
ARBOL N-ARIO
Son aquellos arboles donde el número máximo de hijos por nodo es de N
Árbol Multicamino
Es una estructura de datos homogénea, dinámica y no lineal, en donde cada nodo le pueden seguir la cantidad n de nodos hijos y cada hijo se designa por el número de hijo que le corresponde
Caracterìsticas
Se caracterizan por almacenar sus nodos en forma jerárquica y no en forma lineal, posee un único nodo raíz a excepción de la raíz que esta conectado por medio de una arista o rama a un unico nodo, conocido como nodo padre que les antecede.
Hay un único camino desde la raíz a cada nodo. Todo nodo que no tiene mas ramificaciones se le conoce como nodo terminal hoja.
Teoremas de Euler (Paola V, Fernando , JE)
Camino Euler
Circuito de Euler
Hamilton (andrea,enrique,jose Angel )
Camino Hamiltoniano
Definición
Pasa a través de cada uno de los vértices exactamente una vez.
Cada nodo tiene un grado >= 2
Circuito de Euler. Un circuito de Euler es un circuito que incluye todos lados y por lo tanto todos los vértices de un grafo dado una y solo una vez.
1) Un grafo no dirigido G tiene un paseo de Euler si y solo si tiene cero o dos vértices de valencia impar.
2) Si un grafo no dirigido G tiene un circuito de Euler entonces todo vértice de G tiene valencia par, además de ser conexo.
3) Si G es un grafo no dirigido con vértices {v1, v2, ..., vn} y la suma (v1), (v2), ..., (vn) es par, entonces el grafo tiene un circuito de Euler.
4) Un grafo G tiene un camino de Euler de v w si y solo si v y w son los únicos vértices de valencia impar.
Teorema: Sea G un grafo o multigrafo no dirigido. Entonces G tiene un camino de Euler si, y solo si, es conexo y tiene solo dos vértices de grado impar. Diremos que el grafo es semi-Euleriano.
Es un camino de Euler con la
diferencia
que empieza y termina en el mismo vértice es decir es un camino cerrado que recorre cada arista exactamente una vez.
Es aquel que comienza desde un vértice y encuentra todos sus nodos accesibles y las relaciones en conjunto que permiten que se conecten dichos nodos con el menor peso posible.
Es un algoritmo de búsqueda para lo cual recorre los nodos de un grafo. Su funcionamiento consiste en ir expandiendo cada uno de los nodos que va localizando, de forma recurrente (desde el nodo padre hacia el nodo hijo).
Es un algoritmo de búsqueda para lo cual recorre los nodos de un grafo, comenzando en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo), para luego explorar todos los vecinos de este nodo.
Un árbol binario de búsqueda(ABB) es un árbol binario con la propiedad de que todos los elementos almacenados en el subárbol izquierdo de cualquier nodo x son menores que el elemento almacenado en x ,y todos los elementos almacenados en el subárbol derecho de x son mayores que el elemento almacenado en x.
