informatica

3.3.2 MATRIZ DE INCIDENCIA
Una matriz de incidencia de un grafo es aquella que cumple con las
siguientes condiciones:


Ningún vértice está conectado consigo mismo.



Uno y otro vértice están unidos, a lo más por un solo borde.

A la matriz de incidencia la denotamos por HG.
La matriz de incidencia de un grafo simple G con n vértices {
aristas
y

es la matriz n x k,

dondesi

y k

es incidente con

en caso contrario.

NOTA: en la matriz de incidencia hacemos el estudio del número de aristas que
hay de un vértice a otro, y lo hacemos a través de las cadenas.

3.6.4 RECORRIDOS
Existen dos recorridos básicos que se pueden realizar en los grafos:
1. Un recorrido de amplitud
2. Un recorrido de profundidad.
RECORRIDO DE AMPLITUD.
Es considerado porniveles, donde cada nivel está identificado.
Para recorrer este grafo por amplitud en un lenguaje de programación se lo
hará implementando una estructura de colas en donde se colocan los nodos
correspondientes a cada nivel del grafo. Estos nodos son tratados uno por uno,
luego sus nodos adyacentes son visitados, y a así sucesivamente hasta que
todos los nodos hayan sido visitados. Esta condiciónde terminación se alcanza
cuando la cola queda vacía.
1,2,3,4,5,6,7,8(procesa todos los nodos del mismo nivel)

1,3,2,4,6,5,4,7,8
RECORRIDO EN PROFUNDIDAD.
El recorrido por profundidad sigue primero una trayectoria desde el nodo inicial
hasta un nodo terminal, después otra trayectoria desde el mismo punto inicial
hasta alcanzar otro final., y así sucesivamente hasta que todos los nodoshayan sido visitados.
1,2,4,8,5,7,3,6
1,3,6,7,8,2,5,4
MODELOS DE REDES
RED DE PETRI
Las redes de Petri representan una alternativa para modelar sistemas,
sus características hacen que, para algunos problemas las redes de Petri
funcionen

de

una

manera

natural.

Las redes de petri como ahora conoceremos a las redes de Petri (Petri Net)
fueron inventadas por el alemán Karl AdamPetri en 1962. En su tesis doctoral
"kommunikation mit automaten" (Comunicación con autómatas), establece los
fundamentos para el desarrollo teórico de los conceptos básicos de las redes
de petri.

Las redes petri son consideradas una herramienta para el estudio de
los sistemas. Con su ayuda podemos modelar el comportamiento y la
estructura de un sistema, y llevar el modelo a condicioneslímite, que en un
sistema real son difíciles de lograr o muy costosas. La teoría de la red petri ha
llegado a ser reconocida como una metodología establecida en la literatura de
la

robótica

para

modelar

los

sistemas

de

manufactura

flexibles.

Comparada con otros modelos de comportamiento dinámico gráficos,
como los diagramas de las máquinas de estados finitos, las redes depetri
ofrecen una forma de expresar procesos que requieren sincronía. Y quizás lo
más importante es que las PN pueden ser analizadas de manera formal y
obtener información del comportamiento dinámico del sistema modelado.

Para modelar un sistema se usan representaciones matemáticas logrando una
abstracción del sistema, esto es logrado con las PN, que además pueden ser
estudiadas comoautómatas e investigar sus propiedades matemáticas.

Las redes de Petri se utilizan para modelizar el comportamiento dinámico de
sistemas discretos.
Se componen de dos tipos de objetos:


Las plazas que permiten representar los estados del sistema mediante la
utilización de marcas.



Las transiciones que representan el conjunto de acciones a realizar
cuando se cumplen unas determinadasprecondiciones en el sistema.
Mediante una red de Petri puede modelizarse un sistema de evolución

en paralelo compuesto de varios procesos que cooperan para la realización de
un objetivo común. : Una red de Petri es un conjunto formado por R={P, T, Pre,
Post}
P:

Conjunto

de

plazas

de

cardinal

n.

definida

como:

T: Conjunto de transiciones de cardinal m.
Pre:...