Complejidad Computacional

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cálculo para resolver un problema. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que esta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.

Hoy en día las máquinas resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en el conjunto P. Los problemas con coste factorial o combinatorio están agrupados en NP. Estos problemas no tienen una solución práctica, es decir, una máquina no puede resolverlos en un tiempo razonable.

Tasa de crecimiento:

La tasa de crecimiento de una función mide el rendimiento asintótico de la función, conforme la entrada va creciendo intuitivamente la tasa de crecimiento se determina por el elemento más significativo de la misma.

O(1)=Constante

O(log(n))=Logaritmico

O(n)=Lineal

O(n log(n))=n log n

O(n^2)=Cuadratica

O(n^3)=Cúbica

O(n^r)=Polinomial r>=0

O(b^n)=Exponencial b>1

O(n!)=Factorial

Crecimiento de las funciones más comunes:

n	log2(n)	n2	n3	2n	n!
5	2	25	125	32	120
10	3	100	1000	1024	3628800
20	4	400	8000	1048576	2.43E+18
30	5	900	27000	1.00E+08	2.65E+32
40	5	1600	64000	1.1E+12	8.16E+47
50	6	2500	125000	1.1E+15	3.04E+64
100	7	10000	1000000	1.3E+30	9.33E+157
200	8	40000	8000000	1.6E+60	>10^374

Turing Machine

Una máquina de Turing con una sola cinta puede ser definida como una 6-tupla , donde

• es un conjunto finito de estados.
  
• es un conjunto finito de símbolos de cinta, el alfabeto de cinta.
• es el estado inicial.
• es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.
• es el conjunto de estados finales de aceptación.
• es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.

La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:

* avanzar el cabezal lector/escritor para la derecha.
* avanzar el cabezal lector/escritor para la izquierda.

El cómputo es determinado a partir de una tabla de estados de la forma:

(estado, valor) \rightarrow (\nuevo estado, \nuevo valor, dirección)

Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a ser escrito en la cinta.

Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.

Mediante este modelo teórico y el análisis de complejidad de algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómico son encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.



Esta Maquina de Turing es Capaz de representar la expresion {a^nb^nc^n n>=0} lo cual un automata de pila no puede hacer haciendo utilización de una sola pila.

Análisis Sintáctico

Un analizador sintáctico en informática y linguística es un proceso que analiza secuencias de tokens para determinar su estructura gramatical respecto a una gramática formal dada.

Un parser es así mismo un programa que reconoce si una o varias cadenas de caracteres forman parte de un determinado lenguaje, es utilizado, por ejemplo, en la construcción de compiladores.
El análisis sintáctico convierte el texto de entrada en otras estructuras (comunmente árboles), que son mas útiles para el posterior análisis y capturan la jerarquía implícita de la entrada. Los analizadores léxicos crean tokens de una secuencia de caracteres de entrada y son estos tokens los que son procesados por el analizador para construir la estructura de datos, por ejemplo un árbol de análisis o árboles abstractos de sintaxis.

El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es equivalente en capacidad computacional a un autómata de pila.

El compilador de compiladores que utilicé fue yacc.py, eneguida su descripción:

yacc.py is used to parse language syntax. Before showing an example, there are a few important bits of background that must be mentioned. First, syntax is usually specified in terms of a BNF grammar. For example, if you wanted to parse simple arithmetic expressions, you might first write an unambiguous grammar specification like this:

expression : expression + term
      | expression - term
      | term

term       : term * factor
      | term / factor
      | factor

factor     : NUMBER
      | ( expression )

In the grammar, symbols such as NUMBER, +, -, *, and / are known as terminals and correspond to raw input tokens. Identifiers such as term and factor refer to more complex rules, typically comprised of a collection of tokens. These identifiers are known as non-terminals.

The semantic behavior of a language is often specified using a technique known as syntax directed translation. In syntax directed translation, attributes are attached to each symbol in a given grammar rule along with an action. Whenever a particular grammar rule is recognized, the action describes what to do. For example, given the expression grammar above, you might write the specification for a simple calculator like this:

Grammar                          
-------------------------------- 
expression0 : expression1 + term 
       | expression1 - term 
       | term               

term0       : term1 * factor    
       | term1 / factor     
       | factor             

factor      : NUMBER           
       | ( expression )     

A good way to think about syntax directed translation is to simply think of each symbol in the grammar as some kind of object. The semantics of the language are then expressed as a collection of methods/operations on these objects.

Yacc uses a parsing technique known as LR-parsing or shift-reduce parsing. LR parsing is a bottom up technique that tries to recognize the right-hand-side of various grammar rules. Whenever a valid right-hand-side is found in the input, the appropriate action code is triggered and the grammar symbols are replaced by the grammar symbol on the left-hand-side.

LR parsing is commonly implemented by shifting grammar symbols onto a stack and looking at the stack and the next input token for patterns. The details of the algorithm can be found in a compiler text, but the following example illustrates the steps that are performed if you wanted to parse the expression 3 + 5 * (10 - 20) using the grammar defined above:

Step Symbol Stack           Input Tokens         
---- ---------------------  ---------------------
1    $                      3 + 5 * ( 10 - 20 )$ 
2    $ 3                      + 5 * ( 10 - 20 )$ 
3    $ factor                 + 5 * ( 10 - 20 )$ 
4    $ term                   + 5 * ( 10 - 20 )$ 
5    $ expr                   + 5 * ( 10 - 20 )$ 
6    $ expr +                   5 * ( 10 - 20 )$ 
7    $ expr + 5                   * ( 10 - 20 )$ 
8    $ expr + factor              * ( 10 - 20 )$ 
9    $ expr + term                * ( 10 - 20 )$ 
10   $ expr + term *                ( 10 - 20 )$ 
11   $ expr + term * (                10 - 20 )$ 
12   $ expr + term * ( 10                - 20 )$ 
13   $ expr + term * ( factor            - 20 )$ 
14   $ expr + term * ( term              - 20 )$ 
15   $ expr + term * ( expr              - 20 )$ 
16   $ expr + term * ( expr -              20 )$ 
17   $ expr + term * ( expr - 20              )$ 
18   $ expr + term * ( expr - factor          )$ 
19   $ expr + term * ( expr - term            )$ 
20   $ expr + term * ( expr                   )$ 
21   $ expr + term * ( expr )                  $ 
22   $ expr + term * factor                    $ 
23   $ expr + term                             $ 
24   $ expr                                    $ 
25   $                                         $    


Ejemplo de un analizador sintactico de una
calculadora en PLY:

import ply.yacc as yacc

# Get the token map from the lexer.
This is required.
from calclex import tokens

def p_expression_plus(p):
'expression : expression PLUS term'
p[0] = p[1] + p[3]

def p_expression_minus(p):
'expression : expression MINUS term'
p[0] = p[1] - p[3]

def p_expression_term(p):
'expression : term'
p[0] = p[1]

def p_term_times(p):
'term : term TIMES factor'
p[0] = p[1] * p[3]

def p_term_div(p):
'term : term DIVIDE factor'
p[0] = p[1] / p[3]

def p_term_factor(p):
'term : factor'
p[0] = p[1]

def p_factor_num(p):
'factor : NUMBER'
p[0] = p[1]

def p_factor_expr(p):
'factor : LPAREN expression RPAREN'
p[0] = p[2]

# Error rule for syntax errors
def p_error(p):
print "Syntax error in input!"

# Build the parser
yacc.yacc()

# Use this if you want to build the parser using SLR instead of LALR
# yacc.yacc(method="SLR")

while 1:
try:
   s = raw_input('calc > ')
except EOFError:
   break
if not s: continue
result = yacc.parse(s)
print result

Analisis Léxico

El análisis léxico consiste en convertir una secuencia de caractéres en una secuencia de tokens, para esto se considera en un principio una sola cadena a la cuál se tiene que depurar quitando espacios, tabulaciones, saltos de linea y comentarios. Una vez teniendo los lexemas se trata de relacionar o dar significado, asociandolo a un tipo de token.

Un token se define como un bloque de texto, habitualmente indivisible conocido como lexema. Un analizador léxico procesa los lexemas y los categoriza de acuerdo a su función, dándole asi significado, está asignacion se conoce como "tokenización".

El programa que hace este trabajo se le llama analizador léxico o lexer, PLY es uno que utilizaré en este curso para generar mi Lexer.

Los tokens se definen en muchos analizadores léxicos mediante Expresiones regulares, al leer la cadena la categoriza en tokens, si encuentra un error lo reporta. Consiguiente al Tokenizer sigue el Parser, que se encarga de verificar la estructura de los tokens, esto es llamado análisis sintáctico.

lex.py se usa para tokenizar una cadena de entrada. Por ejemplo suponga que está creando su lenguaje de programación y el usuario proporciona la siguiente cadena.

x = 3 + 42 * (s - t)

El Tokenizer divide la cadena en tokens de la siguiente forma:

'x','=', '3', '+', '42', '*', '(', 's', '-', 't', ')'

En Pyhon Lex se utilizan mayúsculas para indicar un token.

'ID', 'EQUALS', 'NUMBER', 'PLUS', 'NUMBER', 'TIMES',
'LPAREN', 'ID', 'MINUS','ID', 'RPAREN'


Especificamente, la entrada se quiebra en una tupla doble que indica el tipo y valor del token.

('ID','x'), ('EQUALS','='), ('NUMBER','3'),
('PLUS','+'), ('NUMBER','42), ('TIMES','*'),
('LPAREN','('), ('ID','s'), ('MINUS','-'),
('ID','t'), ('RPAREN',')'

Ejemplo de Tokenizer en Python utilizando la libreria PLY.
Este simple tokenizer sirve para definir los tokens de una calculadora.

#----------------------------------------------------------
# calclex.py
#
# tokenizer for a simple expression evaluator for
# numbers and +,-,*,/
# ------------------------------------------------------------
import ply.lex as lex

# List of token names. This is always required
tokens = (
'NUMBER',
'PLUS',
'MINUS',
'TIMES',
'DIVIDE',
'LPAREN',
'RPAREN',
)

# Regular expression rules for simple tokens
t_PLUS = r'\+'
t_MINUS = r'-'
t_TIMES = r'\*'
t_DIVIDE = r'/'
t_LPAREN = r'\('
t_RPAREN = r'\)'

# A regular expression rule with some action code
def t_NUMBER(t):
r'\d+'
try:
t.value = int(t.value)
except ValueError:
print "Line %d: Number %s is too large!" % (t.lineno,t.value)
t.value = 0
return t

# Define a rule so we can track line numbers
def t_newline(t):
r'\n+'
t.lexer.lineno += len(t.value)

# A string containing ignored characters (spaces and tabs)
t_ignore = ' \t'

# Error handling rule
def t_error(t):
print "Illegal character '%s'" % t.value[0]
t.lexer.skip(1)

# Build the lexer
lex.lex()

To use the lexer, you first need to feed it some input text using its input() method. After that, repeated calls to token() produce tokens. The following code shows how this works:

# Test it out
data = '''
3 + 4 * 10
+ -20 *2
'''

# Give the lexer some input
lex.input(data)

# Tokenize
while 1:
tok = lex.token()
if not tok: break # No more input
print tok

When executed, the example will produce the following output:

$ python example.py
LexToken(NUMBER,3,2,1)
LexToken(PLUS,'+',2,3)
LexToken(NUMBER,4,2,5)
LexToken(TIMES,'*',2,7)
LexToken(NUMBER,10,2,10)
LexToken(PLUS,'+',3,14)
LexToken(MINUS,'-',3,16)
LexToken(NUMBER,20,3,18)
LexToken(TIMES,'*',3,20)
LexToken(NUMBER,2,3,21)


The tokens returned by lex.token() are instances of LexToken. This object has attributes tok.type, tok.value, tok.lineno, and tok.lexpos. The following code shows an example of accessing these attributes:

# Tokenize
while 1:
  tok = lex.token()
  if not tok: break      # No more input
  print tok.type, tok.value, tok.line, tok.lexpos

Push down automata

Un autómata de pila es una séptupla:
AP = (Σ, Γ, Q, A0, q0, f, F) donde:
Σ es el alfabeto de símbolos de entrada
Γ es el alfabeto de símbolos de pila
Q es un conjunto finito de estados
A0 ∈ Γ es el símbolo inicial de la pila (un único símbolo)
q0 ∈ Q es el estado inicial del autómata
F es el conjunto de estados de aceptación o estados finales
f es la función de transición de ternas (estado, símbolo de entrada o λ, símbolo de pila) en el conjunto de las partes Q × Γ*


Caracteristicas:

• Ayudan a representar lenguajes que son difíciles o imposibles de representar con Autómatas Determinísticos.
• Los autómatas de pila son capaces de representar cualquier lenguaje independiente de contexto.
• Al cambiar de estado también cambia la cima de la pila.
• Alcance de los lenguajes libres de contexto
  Lema de bombeo- muestra como en algunos lenguajes independientes del contexto pueden producirse cadenas “bombeando” porciones de otras cadenas.
• Si L es un lenguaje independiente de contexto que contiene un número infinito de cadenas, entonces debe existir en L una cadena que tenga la forma svuwt, donde s, v, u, w y t son subcadenas, por lo menos una de v y w es no vacía, y svnuwnt está en L para cada

Representación de {a^n b^n }

M:(
Σ={a,b},
Γ={A,B},
Q= {q0, q1},
A0=Z,
q0=q0,
F=q3,
f(q0, a, λ)={[q0,A]},
f(q0, b, A)={[q1, λ]},
f(q1, b, A)={[q1, λ]})

The Chomsky hierarchy

Introduction:

• Noam Chomsky proposed syntactic models of natural languages.
• The Chomsky hierarchy is a containment hierarchy of classes of formal grammars.
• Four families of grammars make up the chomsky hierarchy

Formal definition of Gramar:

A formal grammar G = (N; Σ ; P; S) consists of:
A finite set N of nonterminal symbols;
A finite set Σ of terminal symbols not in N;
A finite set P of production rules of the form u→v, where u and v are strings in (Σ U N) and u contains at least one non-terminal symbol;
a start symbol S in N.

• A formal grammar defines (or generates) a formal language, which is a set of sequences of symbols that may be constructed by applying production rules to a sequence of symbols which initially contains just the start symbol.

• A rule may be applied to a sequence of symbols by replacing an occurrence of the symbols on the left-hand side of the rule with those that appear on the right-hand side

Nonterminals are usually represented by uppercase letters, terminals by lowercase letters, and the start symbol by S
For example, the grammar with terminals {a,b}, nonterminals {S,A,B}, production rules
S → ABS
S → ε (where ε is the empty string)
BA → AB
BS → b
Bb → bb
Ab → ab
Aa → aa
and start symbol S, defines the language of all words of the form a^nb^n.

The Chomsky hierarchy consists of the following levels:

Type – 0 grammars (unrestricted grammars): They include all formal grammars.They generate exactly all languages that can be recognized by a turing machine.

An unrestricted grammar is a quadruple (V; Σ ; P; S) where V is finite set of variables, Σ (the alphabet) is a finite set of terminal symbols, P is a set of productions, and S is a distinguished element of V.

Type – 1 grammars (Context-Sensitive Grammars): The Generate the context sensitive languages.

No restrictions are placed on the left-hand side of the production, but the length of the right-hand is required to be at least that of the left.


Type-2 grammars (context-free grammars): They generate the context-free languages.

Type-3 grammars (regular grammars): They generate the regular languages. Every regular grammar is a context-free grammar.
Such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed by a single nonterminal.

Context Free Grammars

A context free grammar is a quadruple (V; Σ ; P; S)
where V is a finite set of terminal symbols, Σ (the alphabet)
is a finite set of terminal symbols, P is a set of rules,
and S is the start symbol.
A rule is written A->w where A E V and w E (V U ∑)*
A rule of the form A->λ is called a null or λ-rule

Properties of CFG are:

• These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton.
• Context free languages are the theoretical basis for the syntax of most programming languages.

Example of a CFG:
S->AbAbA
A->aA | λ

Generates the language of the grammar a*ba*ba*

Context Free Grammars

A context free grammar is a quadruple (V; Σ ; P; S)
where V is a finite set of terminal symbols, Σ (the alphabet)
is a finite set of terminal symbols, P is a set of rules,
and S is the start symbol.
A rule is written A->w where A E V and w E (V U ∑)*
A rule of the form A->λ is called a null or λ-rule

Properties of CFG are:

• These languages are exactly all languages that can be recognized by a non-deterministic pushdown automaton.
• Context free languages are the theoretical basis for the syntax of most programming languages.

Example of a CFG:
S->AbAbA
A->aA | λ

Generates the language of the grammar a*ba*ba*

Non deterministic Finite Automata

Formalmente se define como una quintupla, (S, Σ, T, s, A), que consiste en:

• Un conjunto finito de estados (S)
• Un conjunto finito llamado alfabeto (Σ)
• Una función de transición T : S × Σ → P(S).
• Un estado perteneciente a S llamdo estado inicial (s ∈ S).
• Un conjunto de estados terminales o de aceptación A.

Esto es muy parecido a la definición de DFA, la relación entre DFA y NFA puede ser mejor comprendida por la siguiente frase "cada automata determinista es uno no determinista." La función de transición especifica una sola transición por cada combinación entre estado y entrada, en un NFA permite cero, una o más transiciones lo cual lo hace ser más sencillo de expresar.

En los apuntes de DFA teniamos un automata "que acepta la cadenas pertenecientes al lenguaje conformado por el alfabeto Σ={A,B,C,D,E} y que termine por ABC", este mismo puede ser representado más sencillo mediante el NFA:

M: La quintupla se define de la siguiente manera,
Q={q0, q1, q2, q3}
Σ={A, B, C, D, E}
s={q0}
F={q3}

T(q0, A)={q0, q1}
T(q0, {B, C, D, E})=q0
T(q1, B)=q2
T(q2, C)=q3

Deterministic Finite Automata

Formalmente se define como una quintupla, (S, Σ, T, s, A), que consiste en:

• Un conjunto finito de estados (S)
• Un conjunto finito llamado alfabeto (Σ)
• Una función llamada "transición" (T : S × Σ → S)
• Un estado perteneciente a S llamdo estado inicial (s ∈ S).
• Un conjunto de estados terminales o de aceptación A.
  

Una DFA se puede considerar como un aceptador de un lenguaje, el lenguaje del automata es simplemente el conjunto de cadenas aceptadas por su computación. Un DFA sólo puede leer la cadena de entrada sin influir en ella, se puede ver como si se tuviera una cinta donde unicamente se puede recorrer una vez al ser leida y posteriormente no tendra efecto en el cálculo.

En cualquier punto de la computación, el resultado depende unicamente del estado actual y de la entrada sin procesar, a esta combinación se le llama configuración de la maquina y se representa por el par ordenado [qi, w], donde qi es el estado actual y w elemento del todas las combinaciones del alfabeto(Σ*) es la entrada sin procesar. la función de transición es la que transforma la configuración de manera continua, hasta llegar a una transición inexistente o un estado final.


para el automata siguiente:

M: La quintupla se define de la siguiente manera,
Q={q0, q1}
Σ={A, B}
F={q1}

T(q0, A)=q1
T(q0, B)=q0
T(q1, A)=q1
T(q0, B)=q0




Este dibujo fue hecho en JFLAP, un applet de Java que usted puede descargar en www.jflap.org




En el siguiente ejemplo tenemos el automata que acepta la cadenas pertenecientes al lenguaje conformado por el alfabeto Σ={A,B,C,D,E} y que termine por ABC:
A veces se pueden llegar a tener estados sin utilidad dentro de un automata, existe un método para minimizar el DFA de tal forma que sólo contenga los estados necesarios. en el siguiente vínculo encotrara la explicación de ello, DFA minimization.

Conceptos matemáticos preliminares

Teoria de Conjuntos:
El concepto de conjunto es intuitivo y podríamos definirlo simplemente como una colección de objetos, Usualmente los conjuntos se representan con una letra mayúscula: A, B, K,...

Llamaremos elemento, a cada uno de los objetos que forman parte de un conjunto, estos elementos tienen carácter individual, tienen cualidades que nos permiten diferenciarlos, y cada uno de ellos es único, no habiendo elementos duplicados o repetidos. Los representaremos con una letra minúscula: a, b, k,...

De esta manera, si es un conjunto, y todos sus elementos, es común escribir:

Conjuntos definidos:

El universo de discurso, conjunto universal o referencial, que normalmente se denota por las letras U, V o E, es un conjunto cuyo objeto de estudio son los subconjuntos del mismo.

Existe además, un único conjunto que no tiene elementos al que se le llama conjunto vacío y que se denota por . Es decir

La característica importante de este conjunto es que satisface todos los elementos posibles no están contenidos en él, es decir

.

Operaciones con Conjuntos:

Unión:

Diagrama de Venn que ilustra

Para cada par de conjuntos A y B existe un conjunto que se denota como el cual contiene todos los elementos de A y de B. De manera más general, para cada conjunto S existe otro conjunto denotado como de manera que sus elementos son todos los tales que . De esta manera es el caso especial donde .

Intersección

Diagrama de Venn que ilustra

Los elementos comunes a y forman un conjunto denominado intersección de y , representado por . Es decir, es el conjunto que contiene a todos los elementos de A que al mismo tiempo están en B:

.

Si dos conjuntos y son tales que , entonces y se dice que son conjuntos disjuntos.

Digrama de Venn que muestra y

Los elementos de un conjunto que no se encuentran en otro conjunto , forman otro conjunto llamado diferencia de y , representado por . Es decir:

.

o dicho de otra manera:

Algunas personas prefieren denotar la diferencia de y como .

Complemento

El complemento de un conjunto A, es el conjunto de los elementos que pertenecen a algún conjunto U pero no pertenecen a A, que lo representaremos por . Es decir

El conjunto complemento siempre lo es respecto al conjunto universal que estamos tratando, esto es, si hablamos de números enteros, y definimos el conjunto de los números pares, el conjunto complemento de los números pares, es el formado por los números no pares. Si estamos hablando de personas, y definimos el conjunto de las personas rubias, el conjunto complementario es el de las personas no rubias.

En vista de que y , entonces

,

de manera que

Grafo
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 subconjuntos de la forma (u,v) tal que , tal que . Para simplificar, notaremos la arista {a,b} como ab.

Un vértice es la unidad fundamental de la que están formados los grafos. Los vértices son tratados como un objeto indivisible y sin propiedades, aunque puedan tener una estructura adicional dependiendo de la aplicación por la cual se usa el grafo; por ejemplo, una red semántica es un grafo en donde los vértices representan conceptos o clases de objetos.

tipos de Grafos:

Grafos Ciclicos

Un grafo ciclico consiste en un sólo ciclo. un grafo ciclico se denota por C_n, donde n es el número de vértices.

Grafos Bipartitos

Un grafo G es bipartito si puede expresarse como (es decir, la unión de

dos grupos de vértices), bajo las siguientes condiciones:

• V₁ y V₂ son disjuntos y no vacíos.
  
• Cada arista de A une un vértice de V₁ con uno de V₂.
  
• No existen aristas uniendo dos elementos de V₁; análogamente para V₂.

Grafos Completos

Un grafo simple es completo si existen aristas uniendo todos los pares posibles de vértices.
El conjunto de los grafos completos es denominado usualmente , siendo el grafo completo de n vértices.

Un K_n, es decir, grafo completo de n vértices tiene exactamente aristas.

Árbol

Un árbol es un grafo dirigido aciclico en el que cada nodo está conectado con un camino simple, partiendo desde el nodo distinguido llamado "raiz". un nodo y es "hijo" de x, y x el "padre" de y, si y es es adyacente y x esta más cercano a la raiz o es la raiz.