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 , 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 .
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 v1, v2, …, vn 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 v1, v2, …, vn 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 e arestas 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
Categoría:Teoría de grafos Categoría:Informática Categoría:Matemática discreta