No hay

TECNOLÓGICO DE ESTUDIOS SUPERIORES DE COACALCO
TESCo


ALUMNO:

RODRIGUEZ REYES


Número de cuenta:

j9888


CARRERA:

I.S.C.

TITULO:

UNIDAD VI



6.1 INTRODUCCION

Los grafos son representaciones de las redes, y por medio de ellos se puede expresar en forma visual y sencilla la relación entre elementos de distinto tipo. Los vértices pueden ser postes,transformadores, teléfonos, ciudades, registros, y carreteras entre otras cosas. Por medio de la teoría de grafos, se pueden aprovechar mejor los recursos eliminando conexiones redundantes y reduciendo costos y distancias.
En computación estos se utilizan para mostrar las relaciones entre archivos, entre registros, entre computadoras y entre redes como lo hace la red de internet.

6.2 PARTES DE UN GRAFO· VÉRTICES (NODOS): se indica por medio de un pequeño círculo y se le asigna un número o letra.
· LADOS (RAMAS O ARISTAS): son las líneas que une un vértice con otro y se les asigna una letra o un número o una combinación de ambos
· LADOS PARALELOS: son aquellas aristas que tienen relación con un mismo de par de vértices
· LAZO: es aquella arista que se la un vértice y regresa a un mismovértice
· VALENCIA DE VERTICE: es el numero de lados que salen o entran a un vértice

6.3 TIPOS DE GRAFOS

· GRAFOS SIMPLES: son aquellos grafos que no tienen lazos ni lados paralelos
· GRAFO COMPLETO DE n VÉRTICES (Kn): es grafo en donde cada vértice esta relacionado con todos los demás sin lazos ni lados paralelos. se indica con Kn donde “n” es el número de vértice del grafo.
· COMPLEMENTODE UN GRAFO (G): es el grafo que le falta al grafo “G” de forma que entre ambos forman un grafo completo de “n” vértices. este grafo no tiene ni lazo ni ramas paralelas
· GRAFO BIPARTIDO: es el grafo que esta compuesto por dos con justos de vértices donde los elementos del conjunto “A” se relacionan con los del conjunto “B”, pero entre los vértices de un mismo conjunto no existe arista que losuna.
· GRAFO BIPARTIDO COMPLETO (Kn, m):es el grafo que esta compuesto por dos conjuntos de vértices uno de ellos A y el otro B, y en el que cada vértice de A esta unido con todo los vértices de B, pero entre los vértices de un mismo conjunto no existe arista que los una.

6.4 REPRESENTACION MATRICIAL

El uso de matrices para representar sistemas de ecuaciones, relaciones o grafos permite unarápida y clara manipulación de la información.
A continuación se describen las representaciones matriciales de los grafos.
· MATRIZ DE ADYACENCIA (Ma): es una matriz cuadrada en la cual los vértices del grafo se indican como filas y como columnas: el orden de los vértices es el mismo que guardan las filas y las columnas de la matriz.
· MATRIZ DE INCIDENCIA (Mi): en esta matriz se colocan losvértices del grafo como filas y las aristas como columnas.

6.5 CAMBIOS Y CIRCUITOS

· CAMBIOS: es una sucesión de lados que van de un vértice X a un vértice W (dichos lados se pueden repetir).
· CIRCUITO (CICLO): es un cambio del vértice W al vértice w, esto es un cambio que regresa al mismo vértice de donde salió.
· CIRCUITO SIMPLE DE LONGITUD n: es aquel camino del vértice W al vértice w quesola mente tiene un ciclo en la ruta que sigue.
· CAMINO SIMPLE DE LONGITUD n: es una sucesión de lados que van de un vértice X a un vértice w, en donde los lados que componen dicho camino son distintos e iguales a n.
· GRAFO CONEXO: es aquel en el que para cualquier par de vértices w, x, distintos entre si, existe un trayecto para ir de w a x.
· CAMINO DE EULER: es aquel camino que recorretodos los vértices pasando por todas las ramas solamente una ves.
· CIRCUITO DE EULER: es aquel ciclo que recorre todos los vértices pasando por todos los lados solamente una ves.
· ALGORITMO DE FLEURY: permite determinar un círculo de Euler.
1.- Verifica que el grafo sea conexo y que todos los vértices tengan valencia par.
2.- Si cumple con la condición anterior, seleccionar un vértice...