gráfico de gráfico –

Representación gráfica de una función.

Consultamos constantemente mapas, planos, diagramas para orientarnos ante la complejidad de las estructuras: trazados urbanos o viarios, circulaciones y circuitos (eléctricos, informáticos, etc.) de un edificio, clasificaciones, horarios, etc. Cada vez, se trata de establecer una ruta o un vínculo materializable entre dos puntos. Todas estas representaciones pueden unificarse gracias a la noción de grafico.

Tipos de gráficos

Un gráfico sencillo G es un conjunto de puntos S, llamados picos, vinculados o no entre ellos por un conjunto debordes POSEE ; se denota G = (S, A), denotándose el número de vértices Card (S) y el de aristas Card (A). Un grafo simple es la representación de una relación binaria simétrica sobre S cuyos vínculos constituyen A. Si esta relación no es simétrica, estos vínculos son entonces arcos dotados de un origen y un extremo; decimos que la gráfica es orientado.

Si hay una sucesión de aristas que conectan dos vértices X y allí de un grafo simple G, esto constituye un cadena Entre X y y; si, además, x=y, es decir, volvemos al punto de partida, constituye un circuito. En un gráfico dirigido, las sucesiones similares de arcos se denominan respectivamente camino y un ciclo. Para estas cuatro nociones, existe la misma medida, su largo, que es el número de aristas o arcos recorridos. Además, se dice cadena, circuito, camino o ciclo. elemental si no pasamos dos veces por el mismo vértice y sencillo si no tomas el mismo borde dos veces.

Si, en un grafo simple, cualquier vértice es conectable por un camino a cualquier otro, este grafo es simplemente relacionada. Un gráfico es completo si algún vértice está conectado a cada uno de los otros. A menudo, tratamos de evitar en un gráfico que dos aristas se encuentren en otro lugar que no sea un vértice. Esto no siempre es posible, pero cuando lo es, el gráfico es planar Mostramos que no puede haber un grafo completo y plano en cuanto el número de vértices es mayor que cinco.

El uso de gráficos

Es común en problemas de búsqueda operacional o cuando se trata de optimizar un conjunto de operaciones. Los grafos se utilizan en particular en la modelización de redes telefónicas, viales, fluviales, etc., o en el establecimiento de cronogramas de proyectos.

Véase también el artículo Teoría de grafos.