Teor A De Grafos


INSTITUTO UNIVERSITARIO DE TECNOLOGÍA
“ANTONIO JOSÉ DE SUCRE”
EXTENSION BARQUISIMETO
MATERIA: ALGEBRA





TEORIA DE GRAFOS





Integrante:
Montañez Manuel
C.I.24353881
Sección:
Informática 78“A” Nocturno


BARQUISIMETO, 2015 ENERO
Teoría de grafos
La teoría de grafos (también llamada teoría de las gráficas) es un campo de estudio de las matemáticas y las ciencias de la computación, queestudia las propiedades de los grafos (también llamadas gráficas, que no se debe confundir con las gráficas que tienen una acepción muy amplia) estructuras que constan de dos partes,el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados (edges en inglés) que pueden ser orientados o no.

Representación matricial de grafos
Matriz de adyacencia
Es una matriz cuadrada en lacual los nodos del grafo se indican como renglones y como columnas. El orden de los nodos es el mismo que guardan los renglones y las columnas de la matriz. Se coloca 1 como elemento de la matriz cuandoexiste una relación entre uno y otro vértice, o bien un 0 cuando no exista relación alguna.
Nota: en una matriz de adyacencia no es posible representar lados paralelos.

Matriz de incidencia
En estamatriz se colocan los nodos del grafo como renglones y las aristas como columnas. En esta matriz si es posible representar lados paralelos. Al sumar los elementos de cada una de los renglones seobtiene la valencia de los nodos, al sumar las columnas es posible distinguir cuando se trata de un lazo ya que su suma es 1.


Grafos euleriano
Un grafo es una representación, un modelo, compuesto por unnúmero determinado de vértices (nodos) y un número de arcos (aristas) que los relacionan, cada arista o arco tiene la capacidad de relacionar dos nodos. La palabra ciclo se emplea en teoría degrafos para indicar un camino cerrado en un grafo, es decir, en que el nodo de inicio y el nodo final son el mismo, como contrapartida un camino hamiltoriano es un camino que recorre todos los vértices...