Sistema Operativo

GRAFOS

Un grafo es una pareja de conjuntos G = (V,A), donde V es el conjunto de vértices, y A es el conjunto de aristas, este último es un conjunto de pares de la forma (u,v) tal que , tal que. Para simplificar, notaremos la arista (a,b) como ab.

QUE ES UN VERTICE:

Los vértices son los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.

Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.

-QUE ES UNA ARISTA:

Son las lineas con las que se unen los vertices de un grafo, los vertices a y b son los extremos.

»Arista Adyacente: 2 aristas son adyacentes si convergen en el mismo vertice.

»Arista Paralelas: Son dos aristas conjuntas si el vertice inicial y final son el mismo.

»Arista Ciclicos: Es la arista que parte de un vertice para entrar en el mismo.

»Cruce: Son 2 aristas que cruzan en un mismo punto.

ARBOL

La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección de elementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.

BOSQUES DE ÁRBOLES.

Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.

Lazo.- Es un arco que se forma al regresar el sentido al mismo punto

Lazo. Es aquella arista que sale de un nodo y regresa al mismo nodo.

. Un árbol consta de un conjunto de nodos en las que además de la propia información contiene dirección de otros nodos de menor importancia o jerarquía y cumple las siguientes condiciones:

a) Existe un nodo raíz

b) El resto de los nodos se distribuye en un número n de subconjuntos distintos.

c) Cada uno de estos subconjuntos es un subárbol de nodo raíz.

Un vértice de grado 1 en un árbol se llama hoja o un nodo terminal, vértice de grado mayor que 1 recibe el nombre de un nodo rama o nodo interno. Por ejemplo, son hojas b,d,c y los vértices a, A,B,C,D son nodos rama

Nodos. Se indican por medio de un pequeño circulo y se le asigna un numero o una letra.

Valencia

El grado o valencia de un vértice es el número de aristas incidentes al vértice. El grado de un vértice x es denotado por grado(x), g(x) o gr(x) (aunque también se usa δ(x), y del inglés d(x) ydeg(x)). El grado máximo de un grafo G es denotado por Δ(G) y el grado mínimo de un grafo G es denotado por δ(G).

...