Flashcards
TEORIA DE GRAFOS
Cards in this deck (17)
- 1IntroducciónLeonhard Euler fue el más grande matemático, filósofo y físico suizo. Nació el 15 de abril de 1707 en Basilea (Suiza).
- 2Teoría de grafosBásicamente juega un papel importante en las ciencias de la computación, tales como inteligencia artificial, lenguajes formales, teoría de cambio y lógica de diseño, gráficos por computadora, sistemas operativos, compiladores, y organización y recuperación de información.
- 3Entre otras aplicaciones la teoría de grafos se utiliza para:.Cartografía (coloreado de mapas)
. Modelado matemático
. Determinación de tiempos en el desarrollo de proyectos
. Urbanistas
. Programación de exámenes en una institución educativa etc. - 4Los elementos de un grafo.Los elemntos de un grafo son los nodos o vértices y las aristas. Cada arista se forma por la unión de dos vértices. En decir, hay una relación entre las aristas y los nodos.
- 5EjemplificaciónPor ejemplo, si se usan grafos para la ejecución de un plan de actividades, los vértices se pueden asociar con las actividades y las aristas corresponderían al tiempo que tarda o a la probabilidad que se tiene para que se realice una actividad.
- 6Concepto de grafoSea V el conjunto no vacío de vértices o nodos y E el conjunto de lados o aristas se dice que G es un grafo, si G= (V, E) es una estructura de datos compuesta por esos dos conjuntos V y E que forman un conjunto de pares ordenados o desordenados de vértices o nodos. Los pares de vértices van entre paréntesis y los pares desordenados, entre llaves.
- 7Grafo dirigidoUn grafo dirigido o un dígrafo está asociado a un par ordenado .Por ejemplo, si w es vértice de partida y v es vértice de llegada, entonces la arista se asocia a la pareja ordenada (w,v), que es diferente de (v,w) ; es decir,
Los vértices de donde parten las aristas se denominan vértices salientes y a donde llegan llaman vértices entrantes. - 8Grafo no dirigidoUn grafo no dirigido es aquel en el cual sus aristas son direccionales, es decir, si una arista conecta dos nodos A y B se puede recorrer tanto en sentido hacia B como en sentido hacia A. Sus aristas son no dirigidas; es decir, un dígrafo está asociado a un par desordenado.
- 9Grafo dirigido con pesoEs aquel grafo dirigido en el que sus aristas tienen una etiqueta, puede ser un nombre, costo ó un valor de cualquier tipo de dato. También a este grafo se le denomina red de actividades, y el número asociado al arco se le denomina factor de peso. Por ejemplo, la distancia que hay de un lugar a otro.
- 10Grafo mixtoEs aquel grafo en el que algunas de sus aristas son dirigidas y otras son no dirigidas
- 11Vértices adyacentesSon 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.
- 12Grado entrante y saliente de un vérticeEl grado entrante de un vértice es el número de aristas que llegan al vértice.
El grado saliente de un vértice corresponde al número de aristas que salen del vértice. - 13Grado de un vérticeSe 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.
- 14Grafos isomorfosDos grafos son isomorfos si existe correspondencia uno a uno entre los nodos de ambos grafos, y además conservan la adyacencia tanto entre los nodos como en la dirección de los lados.
- 15Grafos PlanosSe dice que G es un grafo plano si puede representarse gráficamente sin la intersección de sus aristas. Es decir, un grafo es plano si puede dividirse en regiones no acotadas.
- 16Grafos HomeomorfosDos grafos G1 y G2 son homeomorfos si pueden reducirse a gráficas isomorfas realizando varias reducciones en serie. La reducción en serie se da cuando en una gráfica G las aristas (v, v1) y (v, v2) están en serie, y al hacer reducción en serie desaparece v y solo queda v1, v2.
- 17Grafos particularesGrafo conexo.
Grafo disconexo.
Grafo regular.
Grafo completo.
Grafo fuertemente conexo.
Grafo Bipartito.
Grafo no bipartito
Grafo Bipartito Completo.
Information
- Description
- Flashcards on TEORIA DE GRAFOS, created by Antonio Sáncehz on 21/06/2020.
- Created by
- Antonio Sáncehz
- Views
- 6
- Rating