Grafo

[miniatura|As sete [pontes de Königsberg coas que se exemplificou o primeiro problema de grafos da historia.]]

En matemáticas e ciencias da computación, un **grafo** (do grego *grafos*: debuxo, imaxe) ou gráfica é o principal obxecto de estudo da teoría de grafos. Informalmente, un grafo é un conxunto de obxectos chamados vértices ou nós unidos por enlaces chamados arestas ou arcos, que permiten representar relacións binarias entre elementos dun conxunto.

## Definicións 
As definicións na teoría de grafos varían. As seguintes son algunhas das formas máis básicas de definir grafos e as estruturas matemáticas relacionadas.

### Grafo 
Un **grafo** (ás veces chamado **grafo non orientado** ou **grafo non dirixido** para distinguilo dun grafo orientado, ou tamén chamado **grafo simple** cando se quere distinguir dun multigrafo) é un par , onde  é un conxunto cuxos elementos se chaman *vértices*, e  é un conxunto de pares non ordenados de vértices \{v_1, v_2\}, cuxos elementos se denominan *arestas* (ás veces *ligazóns* ou *liñas*).

### Grafo orientado 
Un **grafo orientado** ou **grafo dirixido** ou **digrafo** é un grafo no que as arestas teñen orientacións.

Nun sentido restrinxido pero moi común do termo, un **grafo orientado** é un par  que comprende:
* , un conxunto de *vértices* (tamén chamados *nós* ou *puntos*);
* , un conxunto de *arestas* (tamén chamadas *arestas orientadas*, *ligazóns orientadas*, *liñas orientadas*, *frechas* ou *arcos*), que son pares ordenados de vértices distintos E \subseteq \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}.

### Gráfico mixto 
thumb|Un grafo mixto con tres vértices, dúas arestas orientadas e unha aresta non orientada.

Un *grafo mixto* é un grafo no que algunhas arestas poden estar orientadas e outras non.

### Grafo ponderado 
thumb|upright=1.2|Un grafo ponderado con dez vértices e doce arestas cos seus pesos

Un *grafo ponderado* ou unha *rede ponderada* é un grafo no que se lle asigna un número (o peso) a cada aresta. 

Eses pesos poden representar, por exemplo, custos, lonxitudes ou capacidades, dependendo do problema que se trate. Estes grafos xorden en moitos contextos, por exemplo no problema do camiño máis curto como o problema do viaxeiro.

## Tipos de grafos 
### Grafo orientado simple 
Unha definición de *grafo orientado simple* é a dun grafo orientado no que como máximo un de  e  poden ser arestas do grafo.

Algúns autores usan definicións con algunha pequena variante. 

### Grafo regular 
Un *grafo regular* é un grafo no que cada vértice ten o mesmo número de veciños, é dicir, cada vértice ten o mesmo grao. Un grafo regular con vértices de grao *k* chámase grafo *k* regular  ou grafo regular de grao *k*.

### Grafo completo 
thumb|upright|Un grafo completo con cinco vértices e dez arestas. Cada vértice ten unha aresta con cada outro vértice.

Un *grafo completo* é un grafo no que cada par de vértices está unido por unha aresta. Un grafo completo contén todas as arestas posíbeis.

### Grafo finito 
Un *grafo finito* é un grafo no que o conxunto de vértices e o conxunto de arestas son conxuntos finitos. No caso contrario, chámase *grafo infinito*.

O máis común na teoría de grafos dáse a entender que os grafos discutidos son finitos. 

### Grafo conexo 
Nun grafo non orientado, un par non ordenado de vértices  chámase *conectado* se un camiño leva de *x* a *y*. En caso contrario, o par non ordenado chámase *non conectado*.

Un *grafo conexo* é un grafo non orientado no que cada par de vértices non ordenados do grafo está conectado. En caso contrario, chámase *grafo non conexo*.

### Grafo bipartito 
Un *grafo bipartito* é un grafo sinxelo no que o conxunto de vértices pode ser particionado en dous conxuntos, *W* e *X*, de xeito que non hai dous vértices en *W* que compartan unha aresta común nin dous vértices en *X* compartan unha aresta común. Alternativamente, é un grafo cun número cromático de 2.

Nun grafo bipartito completo, o conxunto de vértices é a unión de dous conxuntos disxuntos, *W* e *X*, de xeito que cada vértice en *W* é adxacente a cada vértice en *X* pero non hai arestas dentro de *W* ou *X*.

### Grafo camiño 
Un *grafo camiño* ou *grafo linear* de orde  é un grafo no que os vértices poden ser listados nunha orde *v*1, *v*2, …, *v**n* tal que as arestas son os   onde *i* = 1, 2, ..., *n* − 1. Os grafos camiño pódense caracterizar como grafos conexos nos que o grao de todos os vértices é 2 agás dous vértices de grao 1. 

### Grafo plano 
Un *grafo plano* é un grafo cuxos vértices e arestas se poden debuxar nun plano de forma que non se corten dúas das arestas.

### Grafo cíclico 
Un *grafo cíclico* ou *grafo circular* de orde  é un grafo no que os vértices poden ser listados nunha orde *v*1, *v*2, …, *v**n* tal que as arestas son os  onde *i* = 1, 2, …, *n* − 1, máis a última aresta fechando o ciclo . Os grafos cíclicos pódense caracterizar como grafos conexos nos que o grao de todos os vértices é 2. Se un grafo cíclico aparece como un subgrafo doutro grafo daquela é un ciclo ou circuíto nese grafo.

### Árbore 
thumb|Unha árbore finita con 7 vértices: 4 follas (vértices 1, 3, 5, 7) e 3 vértices internos (vértices 2, 4 e 6).
Unha *árbore* é un grafo non orientado no que dous vértices están conectados por *exactamente un* camiño, ou equivalentemente é un grafo conexo acíclico non orientado.

### Poliárbore 
Unha *poliárbore* (ou *árbore orientada* ou *rede únicamente conexa*) é un grafo acíclico orientado (DAG, polas súas siglas en inglés) cuxo grafo non orientado subxacente é unha árbore.

## Características 
Tipicamente, un grafo represéntase graficamente como un conxunto de puntos (vértices ou nós) unidos por liñas (arestas).

Dende un punto de vista práctico, os grafos permiten estudar as interrelacións entre unidades que interactúan as unhas coas outras. Por exemplo, unha rede de computadoras pódese representar e estudar mediante un grafo, no que os vértices representan terminais e as arestas representan conexións (que á súa vez, poden ser cables ou conexións inalámbricas).

Practicamente calquera problema pode ser representado mediante un grafo, e o seu estudo transcende a diversas áreas das ciencias exactas e das ciencias sociais.

## Exemplos 
* O diagrama da dereita é unha representación esquemática do grafo con vértices V = \{1, 2, 3, 4, 5, 6\} e arestas E = \{\{1, 2\}, \{1, 5\}, \{2, 3\}, \{2, 5\}, \{3, 4\}, \{4, 5\}, \{4, 6\}\}.
* En ciencias da computación, os grafos orientados utilízanse para representar coñecemento (por exemplo,  máquinas de estados finitos e moitas outras estruturas discretas.
* Unha relación binaria *R* nun conxunto *X* define un grafo orientado. Un elemento *x* de *X* é un predecesor directo dun elemento *y* de *X* se e só se *xRy*.

## Notas 
## Véxase tamén 
### Bibliografía 
* 
### Ligazóns externas 
* Graph en MathWorld