Grafo
| Colección | Diccionario de Teoría General de Sistemas y Cibernética |
|---|---|
| Autor | Charles François |
| Año | 1992 |
| Vol. (núm.) | 1(1) |
| ID | ◀ 113 ▶ |
| Recomienda leer | Conexidad, Flujo, Estructura, Constricción, Red, Modelo, Elemento, Interrelación, Arista, Camino, Capacidad, Ciclo de un grafo, Circuito, Vértice, Arco |
Representación gráfica de interrelaciones (representadas por arcos) y elementos (representados por puntos, también llamados “nodos” (B. WALLISER - S.M., p. 133)).
Un grafo puede ser:
- no orientado: cuando no se indica el sentido de la circulación de los flujos entre los nodos.
- orientado: cuando se indica el sentido de la circulación de los flujos entre los nodos.
- conexo: cuando existe un camino que une secuencialmente dos elementos por medio de uno o varios arcos.
- fuertemente conexo: cuando existe siempre un arco entre dos elementos cualesquiera del grafo.
(Se simboliza en el dicho popular: “Todos los caminos llevan a Roma”).
Un grafo puede ser más conexo en una de sus regiones que en otras, especialmente si es modelo de la estructura interna de un sistema.
Conviene señalar que, en un grafo, un elemento puede estar conectado consigo mismo.
También en un grafo pueden recorrerse caminos o circuitos y asociarse una cronología a estos recorridos. (Por ejemplo, en la herramienta de planificación conocida como “camino crítico”).
- Árbol
- Grafo conexo finito no orientado y desprovisto de ciclos (Y. KORSHUNOV - F.M.C., p. 65).
- Arco
- Conexión entre dos elementos de un grafo.
- Arco saturado
- Arco portador de su capacidad máxima de transporte de flujo en una red (Y. KORSHUNOV - F.M.C., p. 76).
- Arista
- Segmento que une dos vértices en un grafo (N. KORSHUNOV - F.M.C., p. 64).
- Camino
- Secuencia de arcos en un grafo en la cual el final de cada arco anterior coincide con el comienzo del siguiente (Y. KORSHUNOV - F.M.C., p. 76).
- Camino elemental
- Camino finito en el cual todos los vértices son diferentes a excepción del primero y del último, que coinciden (Y. KORSHUNOV - F.M.C., p. 74).
- Camino mínimo
- El recorrido más corto que une el vértice inicial con el final en un grafo (Y. KORSHUNOV - F.M.C., p. 70).
- Camino sencillo
- Camino en el cual ningún arco se encuentra dos veces. (Y. KORSHUNOV - F.M.C., p. 64).
- Camino (Largo del)
- Número igual al número de arcos que constituyen el camino (Y. KORSHUNOV - F.M.C., p. 64).
- Ciclo de un grafo
- Circuito finito en el cual coinciden los vértices inicial y final de un grafo. (Y. KORSHUNOV - F.M.C., p. 64).
- Circuito
- Secuencia de aristas en un grafo (Y. KORSHUNOV - F.M.C., p. 64).
- Conexión
- Propiedad de un grafo por la cual sus vértices pueden conectarse en circuito (Y. KORSHUNOV - F.M.C., p. 64).
- Contorno
- Camino finito en el cual el vértice inicial del grafo coincide con el final (Y. KORSHUNOV - F.M.C., p. 64).
- Vértice
- Intersección de dos aristas en un grafo. (Equivale a "nodo").
Para más precisiones sobre grafos, ver las obras de Y. KORSHUNOV, G. KREWERAS y otros autores mencionados en Bibliografías I y III.