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

...