Trabajo matematk unid V

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Educación Universitaria

Universidad Politécnica Territorial del Estado Mérida Kléber Ramírez

Programa Nacional de Formación en Informática (PNFI)

Núcleo: Tucani - El Pinar - Estado: Mérida

Trayecto III - Trimestre II “B”

El Pinar, Marzo 2014

ÍNDICE GENERAL

Pág.

Índice de Figuras…………………….……………………………………...

Índice de Tablas……………………………………………………………..

Introducción………………………………………………….………………

Teoría de Grafos:……………………………………………………………

Multigrados.…..............................................................................

Grafos dirigidos ………………….………..……..………………….

Representación de grafos:…………………………………………

 Incidencia……………………………...….………...................

 Adyacencia……………………...……….…………………….

Caminos, grafos conexos y ciclos…………...............................

Grafos Eulerianos y Hamiltonianos………………......................

Distancias en un Grafo……….…………………………………….

Arboles:………………………………………………………………………..

Definiciones, recorrido……………….…….……………………….

Árboles AVL…………………………………………………………...

Rotaciones: árboles B y B+: definiciones y estructura……….

Conclusión…………………………………………………..........................

Referencia Bibliográfica………………………………………………........ 3

3

4

5

7

7

8

8

8

9

12

15

18

18

19

22

25

26

ÍNDICE DE FIGURAS

Pág.

Figura Nº 1: Un Camino...........................................................................

Figura Nº 2: Grafo Conexo.......................................................................

Figura Nº 3: Grafo No Conexo……………………………………………..

Figura Nº 4: Grafo Eulerianos y Hamiltonianos………………………….

Figura Nº 5: Circuito de Euler……………….……….……………………..

Figura Nº 6: Grafos Curvos………………………..…................................

Figura Nº 7: Dodecaedro de Hamilton…………………………………….

Figura Nº 8: Árbol…………………………………………………………….

Figura Nº 9: Árbol Binario Equilibrado (sí es AVL)….……….……………

Figura Nº 10: Árbol B……………..…........................................................ 10

11

11

13

14

15

16

18

19

20

ÍNDICE DE TABLAS

Pág.

Tabla Nº 1: Grafos, conjuntos, matriz adyacente, matriz de incidencia,

secuencias de grado y listas adyacente……………………..

17

INTRODUCCIÓN

Se dice que un grafo es una estructura matemática que consta de vértices y aristas que conectan estos vértices. Estas estructuras se utilizan para resolver problemas en muchos campos. Por ejemplo, se pueden utilizar para determinar si un circuito se puede implementar de forma plana, para distinguir entre dos componentes químicos con la misma formula molecular pero diferente estructura, etc.

Una de las primeras aplicaciones por ordenador de los grafos estaba relacionada con la planificación de proyectos. Un grafo con aristas dirigidas es una forma natural de describir, representar y analizar proyectos complejos que consten de muchas actividades relacionadas entre si.

Los árboles corresponden a una de las subclases de grafos de uso más amplio, particularmente en computación. Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos. Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente. Por ejemplo, un árbol de definición jerárquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.

Este trabajo de investigación introducirá los siguientes temas: teoría de grafos, estructura, camino Hamiltonianos y Eulerianos y la integración de árboles AVL y árboles B y B+, su definición, estructura, en las computadoras.

TEORÍA DE GRAFOS

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 (gráficos). Sus ideas básicas fueron introducidas en el siglo XVIII por el matemático suizo Leonhard Euler. El grafo es un conjunto de objetos llamados vértices (nodos) y una selección de pares de vértices, llamados aristas. El diagrama de Grafos se representa por una serie de vértices conectados a las aristas.

Los grafos son estructuras discretas ordenadas donde son conjuntos de vértices o nodos conectados por arcos. Existen diferentes tipos de grafos que difieren respecto al número y tipo de arcos que pueden enlazar un par de vértices. En las diferentes áreas de estudio existen algunas dificultades que pueden ser solucionadas utilizando los modelos de grafos.

Además, los grafos son usados para resolver problemas en muchos campos, por ejemplo, se puede utilizar para diferenciar dos compuestos químicos con la misma fórmula molecular pero empleando distintas estructuras; para el caso de nuestra área de interés, un ejemplo es que los grafos pueden ser utilizados para establecer si dos computadoras están conectadas por un enlace de comunicaciones entre las de redes de computadoras.

COMPONENTES DE UN GRAFO

Vértices

Son los nodos con los que se forman los grafos. Los grafos no dirigidos esta formado por un conjunto de vértices y de aristas; y un grafo dirigido esta compuesto por un conjunto de vértices y arcos (pares ordenados de vértices).

Se dice que un vértice es:

• Adyacente: si tenemos un par de vértices de un grafo (U, V), y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.

• Aislado: es el vértice de grado cero.

• Terminal: vértice de grado 1

Un vértice de corte es aquel que al removerlo desconecta al grafo restante. Un conjunto independiente es un conjunto de vértices tal que ninguno es adyacente a otro, y una cobertura de vértices que incluye los puntos finales de cada arista de un grafo.

Aristas

Es la relación que tienen dos vértices de un grafo. Las aristas se representan como una línea que une a dos vértices (esto es para grafos no dirigidos); si el grafo es dirigido, entonces la arista se representa como una flecha.

Lazos

Se denomina lazo cuando una arista conecta a un mismo vértice.

Valencia:

El grado de valencia de un vértice es el numero de aristas incidentes en el. Para un grafo con bucles, estos son contados por dos. En un diágrafo, podemos distinguir el grado saliente (el numero de aristas que dejan el vértice) y el grado entrante (el numero de aristas que entran en un vértice). El grado de vértice seria la suma de ambos números.

TIPOS DE GRAFOS

Grafo simple:

O simplemente grafo es aquel que acepta una sola una arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.

Multigrafo:

O pseudografo son grafos que aceptan más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos no-dirigido.

Grafo dirigido:

Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha

Grafo etiquetado:

Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.

Grafo aleatorio:

Grafo cuyas aristas están asociadas a una probabilidad.

Hipergrafo:

Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.

Grafo infinito:

Grafos con conjunto de vértices y aristas de cardinal infinito.

REPRESENTACIÓN DE GRAFOS

Existen

...