Scribd
Cargar
622 vistas2 páginas

Introducción a la teoría de grafos

La teoría de grafos estudia las propiedades de grafos, que son conjuntos de vértices y aristas. Un grafo se representa como puntos conectados por líneas. El trabajo de Euler sobre los puentes de Königsberg en 1736 es considerado el primer resultado de la teoría de grafos. Existen diferentes formas de representar grafos en una computadora, como listas y matrices. Los grafos pueden ser no dirigidos, donde las aristas no tienen orientación, o dirigidos, donde las aristas tienen una orientación de un vértice de origen a uno de destino

Cargado por

meybelbel_90
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
622 vistas2 páginas

Introducción a la teoría de grafos

La teoría de grafos estudia las propiedades de grafos, que son conjuntos de vértices y aristas. Un grafo se representa como puntos conectados por líneas. El trabajo de Euler sobre los puentes de Königsberg en 1736 es considerado el primer resultado de la teoría de grafos. Existen diferentes formas de representar grafos en una computadora, como listas y matrices. Los grafos pueden ser no dirigidos, donde las aristas no tienen orientación, o dirigidos, donde las aristas tienen una orientación de un vértice de origen a uno de destino

Cargado por

meybelbel_90
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

Grafos resumen

En matemáticas y en ciencias de la computación, la teoría de grafos


(también llamada teoría de las gráficas) estudia las propiedades de
los grafos (también llamadas gráficas). Un grafo es un conjunto, no
vacío, de objetos llamados vértices (o nodos) y una selección de
pares de vértices, llamados aristas (edges en inglés) que pueden
ser orientados o no. Típicamente, un grafo se representa mediante
una serie de puntos (los vértices) conectados por líneas (las
aristas).
El trabajo de Leonhard Euler, en 1736, sobre el problema de
los puentes de Königsberg es considerado el primer resultado de la
teoría de grafos. También se considera uno de los primeros
resultados topológicos en geometría (que no depende de ninguna
medida).

Estructuras de datos en la representación de grafos.


Existen diferentes formas de almacenar grafos en una
computadora. La estructura de datos usada depende de las
características del grafo y el algoritmo usado para manipularlo.
Entre las estructuras más sencillas y usadas se encuentran las
listas y las matrices, aunque frecuentemente se usa una
combinación de ambas. Las listas son preferidas en grafos
dispersos porque tienen un eficiente uso de la memoria. Por otro
lado, las matrices proveen acceso.

Tipos de grafos

Existen dos tipos de grafos los no dirigidos y los dirigidos.

• No dirigidos: son aquellos en los cuales los lados no están


orientados (No son flechas). Cada lado se representa entre
paréntesis, separando sus vértices por comas, y teniendo en cuenta
(Vi,Vj)=(Vj,Vi).

• Dirigidos: son aquellos en los cuales los lados están orientados


(flechas). Cada lado se representa entre ángulos, separando sus
vértices por comas y teniendo en cuenta <Vi ,Vj>!=<Vj ,Vi>. En
grafos dirigidos, para cada lado <A,B>, A, el cual es el vértice
origen, se conoce como la cola del lado y B, el cual es el vértice
destino, se conoce como cabeza del lado.

También podría gustarte