Tipos de grafos
Páginas: 3 (555 palabras)
Publicado: 23 de octubre de 2010
TIPOS DE GRAFOS
Grafo
Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v)tal que , tal que . Para simplificar, notaremos la arista (a,b) como ab.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a quévértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red decarreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad
Grafos simples [editar]
Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto esequivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina GRAFO COMPLEJO.. Un grafo simple está formado por dos conjuntos:
•Un conjunto V de puntos llamados vértices o nodos.
• Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.
De una manera más informalpodemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, Grafos conexos [editar]
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquierpar de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, esconexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda enprofundidad (DFS).
En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una...
Grafo
Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v)tal que , tal que . Para simplificar, notaremos la arista (a,b) como ab.
En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a quévértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.
Muchas redes de uso cotidiano pueden ser modeladas con un grafo: una red decarreteras que conecta ciudades, una red eléctrica o la red de drenaje de una ciudad
Grafos simples [editar]
Un grafo es simple si a lo sumo sólo 1 arista une dos vértices cualesquiera. Esto esequivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina GRAFO COMPLEJO.. Un grafo simple está formado por dos conjuntos:
•Un conjunto V de puntos llamados vértices o nodos.
• Un conjunto de pares de vértices que se llaman aristas o arcos y que indican qué nodos están relacionados.
De una manera más informalpodemos decir que un grafo es un conjunto de nodos con enlaces entre ellos, Grafos conexos [editar]
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquierpar de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es fuertemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, esconexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda enprofundidad (DFS).
En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer en base a él una relación de equivalencia para sus vértices, la cual lleva a una...
Leer documento completo
Regístrate para leer el documento completo.