20 introduccion grafos

Grafos Grafos

Apoyo SSD5Apoyo SSD5

Mtl Lourdes CahuichMtl Lourdes Cahuich 22

IntroducciónIntroducción

En En matemáticasmatemáticas y y ciencias de la computaciónciencias de la computación, un , un grafografo (del (del griegogriego grafosgrafos: dibujo, imagen) o : dibujo, imagen) o gráficagráfica es es el principal objeto de estudio de la el principal objeto de estudio de la teoría de grafosteoría de grafos. .


Definición informalDefinición informal

Informalmente, un grafo es un conjunto de Informalmente, un grafo es un conjunto de objetos llamados objetos llamados vérticesvértices o o nodosnodos unidos unidos por enlaces llamados por enlaces llamados aristasaristas o o arcosarcos, que , que permiten representar permiten representar relaciones binariasrelaciones binarias entre elementos de un entre elementos de un conjuntoconjunto. .


RepresentaciónRepresentación

Típicamente, un grafo se representa Típicamente, un grafo se representa gráficamente como un conjunto de puntos gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (vértices o nodos) unidos por líneas (aristas). (aristas).


UsosUsos

Desde un punto de vista práctico, los Desde un punto de vista práctico, los grafos permiten estudiar las grafos permiten estudiar las interrelaciones entre unidades que interrelaciones entre unidades que interactúan unas con otras. interactúan unas con otras.


UsosUsos

Por ejemplo, una Por ejemplo, una red de computadorasred de computadoras puede representarse y estudiarse puede representarse y estudiarse mediante un grafo, en el cual los vértices mediante un grafo, en el cual los vértices representan representan terminalesterminales y las aristas y las aristas representan conexiones (las cuales, a su representan conexiones (las cuales, a su vez, pueden ser vez, pueden ser cablescables o o conexiones inalámbricasconexiones inalámbricas).).


Definición formalDefinición formal

Un Un grafografo GG es un es un par ordenadopar ordenado GG = = ((VV,,EE), donde:), donde:1.1. VV es un es un conjuntoconjunto de vértices o nodos, y de vértices o nodos, y

2.2. EE es un conjunto de arcos o aristas, que es un conjunto de arcos o aristas, que relacionanrelacionan estos nodos. estos nodos.

3.3. Normalmente Normalmente VV suele ser suele ser finitofinito. .


Definición formalDefinición formal

Se llama Se llama ordenorden de de GG a su número de a su número de vértices, | vértices, | VV | . | .

Un Un lazolazo o o buclebucle es una arista que es una arista que relaciona al mismo nodo; es decir, una relaciona al mismo nodo; es decir, una arista donde el nodo inicial y el nodo final arista donde el nodo inicial y el nodo final coinciden.coinciden.


Tipos de grafosTipos de grafos

Un Un grafo no dirigidografo no dirigido o o grafo grafo propiamente dichopropiamente dicho



Un Un grafo dirigidografo dirigido o o digrafodigrafo



Grafos ponderados (cada arista tiene un Grafos ponderados (cada arista tiene un peso o valor) peso o valor)


Grafos importantesGrafos importantes

Existen grafos que poseen propiedades Existen grafos que poseen propiedades destacables. Algunos ejemplos básicos destacables. Algunos ejemplos básicos son:son:Grafo nuloGrafo nulo o o vacíovacío: aquel que no tiene : aquel que no tiene

vértices ni aristas. Nótese que algunas vértices ni aristas. Nótese que algunas personas exijen que el conjunto de vértices personas exijen que el conjunto de vértices no sea vacío en la definición de grafo. no sea vacío en la definición de grafo.

Grafo trivialGrafo trivial: aquel que tiene un vértice y : aquel que tiene un vértice y ninguna arista. ninguna arista.

Grafo simpleGrafo simple: aquel que no posee : aquel que no posee buclesbucles. .


Grafos importantesGrafos importantes Grafo completoGrafo completo: grafo simple en el que cada par de : grafo simple en el que cada par de

vértices están unidos por una arista, es decir, vértices están unidos por una arista, es decir, contiene todas las posibles aristas. contiene todas las posibles aristas.

Grafo bipartito completoGrafo bipartito completo: sea (: sea (WW,,XX) una ) una particiónpartición del del conjunto de vértices conjunto de vértices VV, es aquel donde cada vértice , es aquel donde cada vértice en en WW es adyacente es adyacente sólosólo a cada vértice en a cada vértice en XX, y , y viceversa. viceversa.

Grafo bipartitoGrafo bipartito: sea (: sea (WW,,XX) una ) una particiónpartición del conjunto del conjunto de vértices de vértices VV, es aquel donde cada arista tiene un , es aquel donde cada arista tiene un vértice en vértice en WW y otro en y otro en XX. .

Grafo Grafo planarplanar o plano: aquel que puede ser dibujado o plano: aquel que puede ser dibujado en el plano cartesiano sin cruce de aristas. en el plano cartesiano sin cruce de aristas.

Árbol: grafo conexo sin ciclos. Árbol: grafo conexo sin ciclos.


Fuente:Fuente:

WikipediaWikipediahttp://es.wikipedia.org/wiki/Diagrama_sagitalhttp://es.wikipedia.org/wiki/Diagrama_sagital

20 introduccion grafos

Technology