Teoría de Grafos

Unidad 2

Introducción

La teoría de grafos es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados que pueden ser orientados o no.

La teoría de grafos es una rama de la matemáticas discretas y aplicadas, y es una disciplina que unifica diversas áreas como combinatoria, álgebra, probabilidad, geometría de polígonos, aritmética y topología.

En una carrera de ciclistas se marca mediante un grafo los puntos por los cuales deben cruzar los competidores.

Ejemplo

Ruta de la carrera 37

Dejamos solo el grafo

A

B

E

C

F

D

HG

IJ

R1R2

R3

R5

R4

R7R6

R9R8

R10

Identificamos sus partes

VERTICES = {A,B,C,D,E,F,G,H,I,J }

ARISTAS = {R1,R2,R3,R4,R5,R6,R7,R8,R9,R10}

TIPO DE GRAFO

Es un grafo regular de grado 2: ya que sus aristas de cada nodo son las mismas.Grafo simple : por que no tiene lados paralelos ni lazos.Grafo dirigido: ya que las aristas tienen dirección hacia donde van.Cuenta con circuito de Euler

El grafo cuenta con el circuito de Euler ya que el grafo es conexo y todos sus vértices(nodos), tienen la valencia de par.Para saber o determinar si un grafo tiene un camino de Euler se toman en cuenta algunos puntos:

Primero es importante que el grafo sea conexo y que todos sus vertices tengan valencia par, si no cuenta con estas condiciones entonces el grafo NO tiene camino de Euler.

Circuito de Euler

Grafo complemento

A

B

E

C

F

D

H

G

IJ

INTEGRANTES DEL EQUIPO

BRAYAN ONTIVEROS VALENZUELA

DANIEL MORA SALDAÑA