Los sistemas numéricos son muy importantes en computación, aquí veremos los sistemas en base 2, 8 y 16 que son las que más se utilizan en computación; por supuesto con la relación entre la base 10 que es la que utilizamos los seres humanos.
SISTEMAS DE NUMERACIÓN
Un sistema de numeración es un conjunto de símbolos y reglas que se utilizan para representar y operar con cantidades. Sistemas Aditivos:
Los sistemas aditivos son aquellos que acumulan los simbolos de todas las unidades, decenas… como sean necesarios hasta completar el número. Una de sus características es por tanto que se pueden poner los símbolos en cualquier orden, aunque en general se ha preferido una determinada disposición. Han sido de este tipo las numeraciones egipcia, sumeria (de base 60), hitita, cretense, azteca (de base 20), romana y las alfabéticas de los griegos, armenios, judios y árabes.
Sistema Egipcio
Desde el tercer milenio A.C. los egipcios usaron un sistema deescribir los números en base diez utilizando los geroglíficos de la figura para representar los distintos ordenes de unidades.
Sistema Griego:
El primer sistema de numeración griego se desarrolló hacia el 600 A.C. Era un sistema de base decimal que usaba los símbolos de la figura siguiente para representar esas cantidades.
Para representar la unidad y los números hasta el 4 se usaban trazos verticales. Para el 5, 10 y 100 las letras correspondientes a la inicial de la palabra cinco (pente), diez (deka) y mil (khiloi). Por este motivo se llama a este sistema acrofónicos.
Sistemas Híbridos
En estos sistemas se combina el principio aditivo con el multiplicativo.
Sistema Chino:
La forma clásica de escritura de los números en China se empezó a usar desde el 1500 A.C. aproximadamente. Es un sistema decimal estricto que usa las unidades y las distintas potencias de 10. Utiliza los ideogramas de la figura:
y usa la combinación de los números hasta el diez con la decena, centena, millar y decena de millar para según el principio multiplicativo representar 50, 700 ó 3000. El orden de escritura se hace fundamental, ya que 5 10 7 igual podría representar 57 que 75.
Sistema Babilónico:
Entre la muchas civilizaciones que florecieron en la antigua Mesopotámica se desarrollaron distintos sistemas de numeración. En el ssss A.C. se inventó un sistema de base 10, aditivo hasta el 60 y posicional para números superiores
Sistema Maya
Los mayas idearon un sistema de base 20 con el 5 cómo base auxiliar. La unidad se representaba por un punto. Dos, tres, y cuatro puntos servían para 2, 3 y 4. El 5 era una raya horizontal, a la que se añadían los puntos necesarios para representar 6, 7, 8 y 9. Para el 10 se usaban dos rayas, y de la misma forma se continúa hasta el 20, con cuatro rayas.
Un sistema de numeración es un conjunto de reglas y símbolos que permiten representar de forma única los números. Esta representación posibilita la realización de sencillos algoritmos para la ejecución de operaciones aritméticas.
Los sistemas de numeración usados en la actualidad son posiciónales. El valor de una cifra depende tanto de qué dígito es como de la posición que ocupa en el número. Base: Es el número de símbolos distintos que se utiliza para representar un número en un sistema de numeración. Entonces decimos que el sistema de numeración es de esa base. Los símbolos de una determinada base van desde el 0 hasta la base b-1.
Coeficiente: El coeficiente determina el valor de cada símbolo dependiendo de la posición que ocupe con respecto al punto decimal. Por lo tanto a estos sistemas de numeración los llamaremos sistemas de numeración posiciónales, porque el valor de cada cifra dependerá del valor absoluto del símbolo y de la posición relativa que ocupa con respecto al punto decimal.
Los sistemas de numeración actuales son sistemas posiciónales, en los que el valor que representa cada símbolo o cifra, depende de su valor absoluto y de la posición relativa que ocupa la cifra con respecto al resto.
En los sistemas de numeración existe un elemento característico que define el sistema y se denomina base, siendo ésta el número de símbolos que se utilizan para la representación.
Se entiende por base (b) de un sistema de numeración al número de símbolos que se utilizan para la representación. Todos los sistemas usados actualmente usan una base n. En un sistema de numeración de base n existen n símbolos. Al escribir un número en base n, el dígito d en la posición i, de derecha a izquierda, tiene un valor.
En general, un número escrito en base n como dmdm − 1…d2d1 tiene un valor
El sistema decimal:
El sistema de numeración decimal es un sistema posicional. La base del sistema de numeración decimal es 10 y está formado por los dígitos del 0 al 1. Un número en el sistema de numeración decimal lo podemos definir según el teorema fundamental de la numeración de la siguiente forma. Numerob= x0b0+ x1b1 + x2b2 + …. + xn-1bn-1 xi = cifras b = datos n = número de cifras
El sistema binario:
El sistema binario o sistema de numeración en base 2 es también un sistema de numeración posicional igual que el decimal, pero sólo utiliza dos símbolos, el “0” y el “1”. Por lo tanto para poder representar mayor número de información al tener menos símbolos tendremos que utilizar más cifras
§ Cuarteto: Número formado por 4 cifras en base 2 § Bit: Bynary digit § Byte: 8 bits § Kilobyte: 1024 bytes § Megabyte: 1024 kilobytes § Gigabyte: 1025 megabytes
Binario puro
El método de representación de enteros del binario puro consiste en pasar el número entero sin signo a binario, con la particularidad de respetar siempre el tamaño de la representación.
El paso de decimal a binario consiste en dividir por 2 sucesivamente hasta que el cociente sea menor que la base: Con lo que queda 1110 = 10112
Sistema Octal:
Es un sistema de base 8, es decir, con tan solo ocho dígitos posibles, ‘0’ a ‘7’. El paso de octal a decimal se realiza multiplicando cada dígito por su peso: 278 = 2 •81 + 7 • 80 = 2310 El paso inverso consiste en dividir por la base (8): Con lo que queda 678 = 10310
Sistema Hexadecimal:
Sin embargo el sistema de numeración más utilizado es el hexadecimal, el cual consta de 16 dígitos diferentes {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}.
El paso de hexadecimal a decimal es análogo a los anteriores: 12316 = 1 • 162 + 2 • 161 + 3 • 160 = 29110 Al igual que el paso de decimal a hexadecimal: Con lo que queda 2910 = 12316
lunes, 7 de diciembre de 2009
Arboles Generadores
Un árbol T, subgrafo de un grafo G que contenga todos los vértices de G se denómina Arbol Generador de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es asi como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.
ARBOLES GENERADORES
Debido a que los arboles son estructuras mas simples de manejar que los grafos, es conveniente cuando tenemos un grafo conexo, construir un árbol que contenga todos los nodos: de esta forma es posible visitar todos los nodos con una estructura mas eficiente y donde es posible visitar todos los nodos con una estructura mas eficiente y donde es posible implementar de una forma mas directa los algoritmo para el manejo de la información.
Definición: un árbol generador T de un grafo conexo G un árbol que es subgrafo de G y que contiene todos los nodos.
un árbol generador es: T1=( ( a,b), (a,d),(b,c),(c,f),(d,e) ) El cual lo podríamos dibujar
También el árbol T2 es otro árbol generador T2= ( (b,a),(b,c),(b,c),(b,e),(c,f) )
El cual se puede representar como
Hay varias formas de crear los arboles generadores, dos de las mas comunes e importantes son las de los algoritmos.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es asi como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
En general un grafo G tendrá varios árboles generadores ,como el del ejemplo 1 el cual tiene a lo menos dos arboles generadores T1 yT2.
Algoritmos para hallar un árbol generador , que se base en el teorema de que el grafo G debe ser conexo, pueden ser los que se realizan a través de los métodos llamados buscar primero a lo ancho , buscar primero a lo largo y el de regreso al nivel anterior.
ARBOLES GENERADORES
Debido a que los arboles son estructuras mas simples de manejar que los grafos, es conveniente cuando tenemos un grafo conexo, construir un árbol que contenga todos los nodos: de esta forma es posible visitar todos los nodos con una estructura mas eficiente y donde es posible visitar todos los nodos con una estructura mas eficiente y donde es posible implementar de una forma mas directa los algoritmo para el manejo de la información.
Definición: un árbol generador T de un grafo conexo G un árbol que es subgrafo de G y que contiene todos los nodos.
un árbol generador es: T1=( ( a,b), (a,d),(b,c),(c,f),(d,e) ) El cual lo podríamos dibujar
También el árbol T2 es otro árbol generador T2= ( (b,a),(b,c),(b,c),(b,e),(c,f) )
El cual se puede representar como
Hay varias formas de crear los arboles generadores, dos de las mas comunes e importantes son las de los algoritmos.
Propiedades De Los Arboles
Arboles
Son un tipo especial de grafo.
G es un grafo, no digrafo sin bucles. G es un arbol si es conexo y no tiene ciclos.
Arboles degenerados: Arbol con un solo vertice y sin lados.
Arbol maximal: T es un arbol maximal de un grafo G conexo, si es un arbol y contiene todos los vertices de G.
Teorema 1: Si a y b son dos vertices distintos de un arbol, entonces existe un unico camino elemental que conecta dichos vertices.
Teorema 2: T es un arbol cualquiera, entonces
v=E+1.
Teorema 3: T es un arbol con
v”2, se verifica que tiene almenos dos vertices terminales.
Son un tipo especial de grafo.
G es un grafo, no digrafo sin bucles. G es un arbol si es conexo y no tiene ciclos.
Arboles degenerados: Arbol con un solo vertice y sin lados.
Arbol maximal: T es un arbol maximal de un grafo G conexo, si es un arbol y contiene todos los vertices de G.
Teorema 1: Si a y b son dos vertices distintos de un arbol, entonces existe un unico camino elemental que conecta dichos vertices.
Teorema 2: T es un arbol cualquiera, entonces
v=E+1.
Teorema 3: T es un arbol con
v”2, se verifica que tiene almenos dos vertices terminales.
Arboles
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… Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamados subárboles.
Una forma particular de árbol puede ser la estructura vacía. Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro
Ejemplo de árbol:
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo. Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R. En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A),
V= A+ 1.
Teorema:
Para cualquier árbol R = (V,A), si
A
›= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
G es un árbol.
G es conexo y no contiene circuitos.
G es conexo y tiene (n-1) lados.
G no contiene circuitos y tiene (n-1) lados.
Arboles con Raíz
Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, …, vn), es un camino en G.
V(n-1) es el padre de v(n).
V0, v1, …, v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.
Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si
V › 1, sean R1, R2, R3, …., Rk los subarboles de R según se va de izquierda a derecha.
El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.
El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,…., Rk en orden simétrico.
El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,…., Rk en orden posterior y a continuación por la raíz.
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.
Teorema:
Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.
Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.
Arboles generadores:
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
Una forma particular de árbol puede ser la estructura vacía. Un árbol es un grafo simple en el cual existe un único camino entre cada par de vértices. Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Los árboles pueden ser construidos con estructuras estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras que las dinámicas están representadas por listas. Sea G =(V,A) un grafo no dirigido. G se denomina ARBOL, si es conexo y no contiene ciclos. Un árbol con raíz, es un árbol que tiene un vértice particular designado como raíz.
Se utiliza la recursión para definir un árbol porque representa la forma más apropiada y porque además es una característica inherente de los mismos. Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, para el análisis de circuitos eléctricos y para numerar los capítulos y secciones de un libro
Ejemplo de árbol:
En la figura anterior G1 corresponde a lo que llamamos mediante la definición ARBOL, en el caso de G2, éste no corresponde debido a que contiene un ciclo. Podemos destacar que cuando un grafo G es un Arbol, se reemplaza G, por R. En la figura mostrada G1 es un subgrafo de G2, en el que G1 contiene los vértices de G2 y es árbol, además lo llamaremos “árbol abarcador”, por que proporciona conexión minimal para el grafo y un esqueleto minimal que une los vértices.
Ejemplo de árbol raíz:
Para apoyar el entendimiento de las definiciones entregadas agregaremos algunos teoremas.
Teorema:
Si a, b son vértices de un árbol R (V,A), entonces hay un camino único que conecta estos vértices.
Teorema:
En cualquier árbol R= (V,A),
V= A+ 1.
Teorema:
Para cualquier árbol R = (V,A), si
A
›= 2, entonces R tiene al menos dos vértices colgantes.
Teorema:
Sea G un grafo simple con v vértices, entonces se puede decir:
G es un árbol.
G es conexo y no contiene circuitos.
G es conexo y tiene (n-1) lados.
G no contiene circuitos y tiene (n-1) lados.
Arboles con Raíz
Sea G un grafo dirigido, se denomina “árbol dirigido” si el grafo no dirigido asociado con G es un árbol. Cuando G es un árbol dirigido, se denomina “árbol con raíz” si hay un único vértice r, la raíz.
Sea G un grafo con raíz V0. Supóngase que x, y, z son vértices en G y que (v0, v1, …, vn), es un camino en G.
V(n-1) es el padre de v(n).
V0, v1, …, v(n-1) son los antepasados de v(n).
V(n) es el hijo de v(n-1).
Si x es un antepasado de y, entonces y es un descendiente de x.
Si x e y son hijos de z entonces x e y son hermanos.
Si x no tiene hijos entonces x es un vértice terminal.
Si x no es un vértice terminal, entonces x es un vértice interno.
El subgrafo de G que consiste en x y todos sus descendientes, con x como raíz, es el subarbol de G que tiene a x como raíz.
Sea R= (V,A) un árbol con raíz r. Si R no tiene otros vértices, entonces la raíz misma constituye el recorrido en orden previo, simétrico y posterior de R. Si
V › 1, sean R1, R2, R3, …., Rk los subarboles de R según se va de izquierda a derecha.
El recorrido de orden previo de R comienza en r y después pasa por los vértices de R1 en orden previo, a continuación por los vértices de R2 en orden previo, y así sucesivamente hasta que se pasa por los vértices de Rk en orden previo.
El recorrido en orden simétrico de R primero, se pasa por los vértices de R1 en orden simétrico, después por la raíz r y a continuación por los vértices de los subarboles R2, R3,…., Rk en orden simétrico.
El recorrido en orden posterior de R pasa por los vértices de los subarboles R1, R2,…., Rk en orden posterior y a continuación por la raíz.
Un árbol binario es uno con raíz en el cual cada vértice tiene un hijo a la derecha o un hijo a la izquierda, o viceversa, o bien ningún hijo. Un árbol binario completo es uno en el cual cada vértice tiene un hijo a la derecha y uno a la izquierda, o bien ningún hijo.
Teorema:
Si T es un árbol binario completo con i vértices internos, entonces T tiene i + 1 vértices terminales y 2i + 1 vértices en total.
Un árbol binario de búsqueda es un árbol binario T donde se han asociado datos a los vértices. Los datos se disponen de manera que para cualquier vértice v en T, cada dato en el subarbol a la izquierda de v es menor que el dato correspondiente a v.
Arboles generadores:
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G.
A esta característica general es posible agregar ciertos teoremas de modo de detallar aún más el alcance de la definición. Es así como el Grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices.
Representacion De Estructura Mediante Grafos
Uno de los aspectos más importantes en computación es la programación. Para elaborar un programa es conveniente tener una forma de representar las ideas antes de elaborar el código. Aquí presentamos una aplicación de los grafos en la representación de los conceptos básicos de diagramas de flujo. Por supuesto que los diagramas de flujo son mucho más generales que su uso en programación y pueden ser utilizados para muchas otras aplicaciones.
Clasificacion De Grafos
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. En un grafo no dirigido el par de vértices que representa un arco no está ordenado. Por lo tanto, los pares (v1, v2) y (v2, v1) representan el mismo arco. En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que y representan dos arcos diferentes.
Ejemplos G1 = (V1, A1) V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)} G3 = (V3, A3) V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Algunos de los principales tipos de grafos son los que se muestran a continuación:
• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular. Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular
• Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
• Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6 • Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices. A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
• Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
• Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior o Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior
Grafos Eulerianos. Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes: El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.
Grafos Conexos. Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
Árboles.
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos). Bosques de árboles. Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.
Ejemplos G1 = (V1, A1) V1 = {1, 2, 3, 4} A1 = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} G2 = (V2, A2) V2 = {1, 2, 3, 4, 5, 6} A2 = {(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)} G3 = (V3, A3) V3 = {1, 2, 3} A3 = { <1, 2>, <2, 1>, <2, 3> }
Algunos de los principales tipos de grafos son los que se muestran a continuación:
• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular. Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular
• Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es
• Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.
A continuación pueden verse los dibujos de K3, K4, K5 y K6 • Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices. A continuación ponemos los dibujos de K1,2, K3,3, y K2,5
• Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
• Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior o Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro. Para ver el gráfico seleccione la opción ¨Bajar trabajo¨ del menú superior
Grafos Eulerianos. Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano. Como ejemplos tenemos las siguientes imágenes: El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.
Grafos Conexos. Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: “un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une”.
Árboles.
Un árbol se define como un tipo de grafo que no contiene ciclos, es decir es un grafo también acíclico, pero a su vez es conexo. Tal es el caso de los siguientes dos grafos en donde se puede notar que ninguno de los dos contiene repeticiones (ciclos). Bosques de árboles. Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.
Conceptos Basicos De Grafos
Aristas: Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une. Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.
→Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
→Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
→Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
→Cruce: Son dos aristas que cruzan en un punto.
Vértices: Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es ‘par’ o ‘impar’ según lo sea su grado.
→Vértices Adyacentes: 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.
→Vértice Aislado: Es un vértice de grado cero.
→Vértice Terminal: Es un vértice de grado 1.
Caminos: Sean x, y Î V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},…, {vn,y}. En este caso
→x e y se llaman los extremos del camino
→El número de aristas del camino se llama la longitud del camino.
→Si los vértices no se repiten el camino se dice propio o simple.
→Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
→Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
→Llamaremos ciclo a un circuito simple
→Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo
→Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
→Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
→Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
→Cruce: Son dos aristas que cruzan en un punto.
Vértices: Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es ‘par’ o ‘impar’ según lo sea su grado.
→Vértices Adyacentes: 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.
→Vértice Aislado: Es un vértice de grado cero.
→Vértice Terminal: Es un vértice de grado 1.
Caminos: Sean x, y Î V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},…, {vn,y}. En este caso
→x e y se llaman los extremos del camino
→El número de aristas del camino se llama la longitud del camino.
→Si los vértices no se repiten el camino se dice propio o simple.
→Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
→Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
→Llamaremos ciclo a un circuito simple
→Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo
Introduccion a La Teoria De Grafos
Problema de los Puentes de Könisberg
Definición: Un grafo G = (N,A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos. Una arista en general se representa por {a,b}.
Una forma de represtar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.
Ejemplo: G = { n1, n2, n3,n4,n5, n6, n7,n8 } , A = { {n1, n2}}, {n1, n5},{n2, n3},{n3, n4} , {n4, n7}, {n2, n6},{n6, n2} } Outline del contenido
Notación: Una arista es un conjunto, pero puede haber dos aristas que conecte los mismos nodos, por lo que se le puede anteponer un nombre, por ejemplo a1(n2, n6) , a2(n2, n6) son dos aritas para unir los nodos n2 y n6. También puede ser que en un arista importe el orden de los nodos por lo que podemos en este caso utilizar la notación de par ordenado (n1, n2). Valencias
Definición: Un grafo G = (N,A) consta de un conjunto de nodos N y un conjunto de aristas A, en donde a cada arista es un par no ordenado de nodos. Una arista en general se representa por {a,b}.
Una forma de represtar grafos es mediante círculos para los nodos, conectados por líneas para las aristas.
Ejemplo: G = { n1, n2, n3,n4,n5, n6, n7,n8 } , A = { {n1, n2}}, {n1, n5},{n2, n3},{n3, n4} , {n4, n7}, {n2, n6},{n6, n2} } Outline del contenido
Notación: Una arista es un conjunto, pero puede haber dos aristas que conecte los mismos nodos, por lo que se le puede anteponer un nombre, por ejemplo a1(n2, n6) , a2(n2, n6) son dos aritas para unir los nodos n2 y n6. También puede ser que en un arista importe el orden de los nodos por lo que podemos en este caso utilizar la notación de par ordenado (n1, n2). Valencias
Teoria De Grafos
En matemáticas y ciencias de la computación, la teoría de grafos estudia las propiedades de los grafos, que son colecciones de objetos llamados nodos (o vértices) conectados por líneas llamadas aristas (o arcos) que pueden tener orientación (dirección asignada).
Suscribirse a:
Entradas (Atom)
