MAPA MENTAL CIRCULAR ESQUEMA

geometría

Profesor: Pacheco Osvaldo.Alumna: Celina Mur.

ARCO

CAMINO

Suege a partir de la resolución de un problema de Euler referido a los puentes del Río Pergel en Rusia en 1736 .

CIRCUITO

DIRIGIDOS

Origen

Según su dirección se clasifican

BUCLE

ARISTA

NO DIRIGIDOS

CADENA

TEORÍA DE GRAFOS

CICLO

Grafo es una abstracción matemática que designaremos por G = (V, A) donde V es un conjunto de puntos, V≠Ø, y A es un conjunto de líneas que unen dos puntos de V; A puede ser vacío (Ø), llamado conjunto de las aristas que están relacionados mediante la aplicación T.

LAZO

Tipos

Definición

GRAFOS

GRAFO

MULTIGRAFO

PSEUDOGRAFO

Según su dirección

Grado de emisión: número de arcos que salen de un punto determinado del grafo dirigido

ArcoCaminoCircuito

Ramificación: Son los puntos cuyo grado de emisión es mayor que uno)

Relación que indica dirección Entre un punto y otro puede haber más de un arco

Camino elemental: Es aquel que nunca pasa más de una vez por un mismo punto

Camino Hamiltoniano: Es el camino elemental que pasa por todos los vértices del grafo

Dirigidos

Es una ruta que se debe seguir para llegar de un punto a otro. Entre un punto y otro puede haber más de un camino

Camino compuesto: Es aquel que utiliza más de una vez un mismo punto

Circuito elemental: camino elemental que vuelve a su punto de partida

Es aquel camino que vuelve a su punto de origen. Todo punto que pertenece a un circuito puede ser punto de partida.Todo punto de partida es a la vez punto de llegada

Circuito compuesto: camino compuesto que vuelve a su punto de partida

Bucle

Circuito Hamiltoniano: un camino que vuelve a su punto de partida pasando por todos los vértices del grafo

Es la conexión de un vértice consigo mismo

Arista

Se obtiene de un arco si omitimos su dirección

Cadena

No Dirigidos

Se obtiene de un camino al omitir su dirección

Ciclo

Lo obtenemos de un circuito, también omitiendo su dirección, es decir, es una cadena cerrada. Todo punto del ciclo puede ser punto de partida Todo punto de partida es un punto de llegada

Lazo

Es una arista cuales extremos inciden sobre el mismo vértice

TIPOGRAFÍA

Un grafo se dice que es plano si y sólo si existe una representación plana del mismo, de forma que las curvas que representan los arcos se cortan sólo en los puntos que representan a los vértices. TEOREMA:Un grafo es plano si y sólo si no contiene como subgrafo a ningún grafo que sea homeomorfo (dos grafos son homeomorfos si ambos pueden obtenerse a partir de un mismo grafo por una sucesión de subdivisiones elementales de aristas)

PLANO

Grafos

Sea (V,A ) un grafo, G es conexo si y solo si para todo par de vértice U y V de G existe un camino en G que conecta U y V TEOREMA: Sea G un grafo conexo. G tiene un camino euleriano no cerrado si y sólo si tiene exactamente dos vértices de grado impar. .

CONVEXO

Es euleriano si tiene un camino euleriano cerrado ( Un camino simple que contenga a todos los arcos de un grafo se dice que es euleriano.) TEOREMA DE EULER: Sea G= (V, A) un grafo con A≠Ø es un grafo euleriano y sin vértices aislados si y sólo si es conexo y todo sus vértices tienen grado par.

EULERIANO

Un grafo G se dice que es un árbol si y sólo si verifica las siguientes condiciones: G es conexo G no posee ciclos. COROLARIO: Un grafo G es un árbol si, y sólo si para todo par de vértices distintos, u ,v de G, existe un único camino simple de extremos u y v.

ÁRBOL

Multigrafo

Es aquel grafo en donde dos vértices se pueden conectar por más de una arista.

Pseudografos

Es aquel multígrafo en donde al menos exista un bucle (un vértice conectado con si mismo

EJEMPLOS

GRAFOS DE LLAMADAS Los grafos se pueden utilizar para representar las llamadas telefónicas hechas en una red, por ejemplo en una red telefónica de larga distancia. En particular, puede usarse un multígrafo dirigido para representar llamadas: cada vértice representa un número de teléfono y cada arista representa una llamada. La arista que representa una llamada sale del número del teléfono desde el que se hace la llamada y llega al número de que lo recibe.

Grafo de la Red La red de Internet se puede representar mediante un grafo dirigido en el que cada página Web está representada por un vértice y en el que una arista comienza en la página a y termina en la página b si hay un enlace en la página a que conduce a la página b.

Red de tráfico con caminos y cruces Los grafos se utilizan también para modelar trayectos como el de una línea de autobús a través de las calles de una ciudad, en el que podemos obtener caminos óptimos para el trayecto aplicando diversos algoritmos como puede ser el algoritmo de Floyd.