Tipos De Grafos

INSTITUTO
TECNOLOGICO DE
PACHUCA

MATEMÁTICAS DISCRETAS

UNIDAD VI

TIPOS DE GRAFOS

PROFESOR:
AGUILAR FLORES NICOLAS RAFAEL

ALUMNA:
AGUILAR DE BLAS RICARDO

INGENIERIA EN SISTEMAS
COMPUTACIONALES

MATUTINO

CAMINOS YCICLOS
Si pensamos los vértices de una grafica como ciudades y las aristas como carreteras, un camino corresponde a un viaje que comienza de unaciudad, pasa por varias ciudades, y termina en alguna ciudad. Primero daremos una definición formal de camino.
CAMINO. Sean v0 y vn vértices de una grafica. Un camino (ruta) de v0 a vn de longitud n es una sensación alternamente de n+1 vértices y n aristas que comienza con el vértice v0 y termina con el vértice vn

En donde la arista e es incidente sobre los vértices vi-1 y v para i=1,.., nPor ejemplo:
(1, e1, 2, e2, 3, e3, 4, e4, 2)
Es un camino de longitud 4 del vértice 1 al vértice 2

Una gráfica conexa es aquella en la cual podemos ir de cualquier vértice a cualquier otro por un camino.
Por ejemplo:
La grafica G de la figura no es conexa pues no existe el del vértice V2 al vértice V5

Una gráfica G es conexa si dados cualesquiera 2 vértices v y w en G, existe uncamino de w a v. Sea G= (V,E) una gráfica, (V’,E’) una subgrafica de G si
a) V' C V y E’ C E
b) Por cada arista e’ϵ E’, si e’ es incidente en v’ y w’, entonces v’, w’ ϵ V’.
Por ejemplo
La grafica G’= (V’, E’) es una subgrafica de G= (V, E) pues V’ C V y E’ C E
Una grafica (o grafica no dirigida) consta de un conjunto V de vértices (o nodos) y un conjunto E de aristas (arcos o lados)tales que cada arista e ϵ E queda asociada a un par no ordenado de vértices. Si existe una única arista e asociada con los vértices v y w, escribimos e= (v,w) o e= (w,v). En este contexto (w,v) denota una arista entre v y w en una grafica no dirigida y no un para ordenado

Por ejemplo:
La figura muestra una grafica dirigida. Las notas dirigidas se indican mediante flechas. La arista e1 seasocia con el par ordenado (v2, v1) de vértices y la arista e7 se asocia con el par ordenado (v6, v6) de vértices. La arista e1 se denota (v2, v1) y la arista e7 se denota (v6, v6)

Una grafica dirigida (o digráfica) G consta de un conjunto V de vértices (o nodos) y un conjunto E de aristas (arcos o lados) tales que cada arista e ϵ E se asocia con un par ordenado de vértices. Si existe unaúnica arista e asociada con el par ordenado (v, w) de vértices escribimos e= (v, w), lo cual denota una arista de v a w.
Por ejemplo.
En la figura, las aristas e1 y e2 esta asociadas con el par de vértices (v1, v2). Tales aristas son paralelas. Una arista incidente en un único vértice es una vértice v4 de la figura de abajo, que no es incidente en arista alguna es un vértice aislado. Una graficasin lazos ni aristas paralelas en una grafica simple

En un proceso de producción, con frecuencia es necesario realizar muchos agujeros en las hojas de metal. Los componentes se pueden atornillar entonces en estas hojas de metal. Los agujeros se pueden realizar bajo el control de una computadora. Para ahorrar el tiempo y dinero el taladro debe moverse lo más rápido posible. Por eso se moldeaeste ejemplo con la grafica de la izquierda
Cada par de vértices se une mediante una arista. En cada arista escribimos el tiempo necesario para mover el taladro entre los agujeros correspondientes una grafica con números en las aristas se llama grafica con pesos. Si la arista e tiene la etiqueta k, decimos que el peso de la arista e es k.

En una grafica con pesos, la longitud de un camino esla suma de los pesos de las aristas en el camino. Por ejemplo en la figura anterior, la longitud de un camino que comienza a, vista c y termina en b es 8. En este problema la longitud de un camino que comienza con el vértice v1, luego visita v2, vy ..., en ese orden y termina en vn representa el tiempo que tarda el taladro en partir del agujero hn, donde el agujero h, corresponde al vértice v7...