Definições na teoria dos gráficos variam. Seguem-se algumas das formas mais básicas de definir gráficos e estruturas matemáticas relacionadas.
GraphEdit
Um gráfico (por vezes chamado gráfico não dirigido para distinguir de um gráfico dirigido, ou gráfico simples para distinguir de um multigráfico) é um par G = (V, E), onde V é um conjunto cujos elementos são chamados vértices (singular: vértice), e E é um conjunto de vértices emparelhados, cujos elementos são chamados arestas (por vezes ligações ou linhas).
Os vértices x e y de uma aresta {x, y} são chamados de vértices finais da aresta. Diz-se que a aresta une x e y e é incidente em x e y. Um vértice pode não pertencer a nenhuma aresta, caso em que não está unido a nenhum outro vértice.
Um multigráfico é uma generalização que permite que múltiplas arestas tenham o mesmo par de vértices finais. Em alguns textos, os multigrafos são simplesmente chamados gráficos.
Por vezes, os gráficos podem conter loops, que são arestas que ligam um vértice a si próprios. Para permitir loops, a definição acima deve ser alterada através da definição de arestas como conjuntos múltiplos de dois vértices em vez de conjuntos de dois. Tais gráficos generalizados são chamados gráficos com loops ou simplesmente gráficos quando é claro a partir do contexto que os loops são permitidos.
Geralmente, o conjunto de vértices V é suposto ser finito; isto implica que o conjunto de arestas é também finito. Os gráficos infinitos são por vezes considerados, mas são mais frequentemente vistos como um tipo especial de relação binária, uma vez que a maioria dos resultados em gráficos finitos não se estendem ao caso infinito, ou necessitam de uma prova bastante diferente.
Um gráfico vazio é um gráfico que tem um conjunto vazio de vértices (e portanto um conjunto vazio de arestas). A ordem de um gráfico é o seu número de vértices |V|. O tamanho de um gráfico é o seu número de vértices |E|. No entanto, em alguns contextos, tais como para expressar a complexidade computacional dos algoritmos, o tamanho é |V| + |E| (caso contrário, um gráfico não vazio poderia ter um tamanho 0). O grau ou valência de um vértice é o número de arestas que lhe são incidentes; para os gráficos com loops, um laço é contado duas vezes.
Num gráfico de ordem n, o grau máximo de cada vértice é n – 1 (ou n se forem permitidos loops), e o número máximo de arestas é n(n – 1)/2 (ou n(n + 1)/2 se forem permitidos loops).
As arestas de um gráfico definem uma relação simétrica nos vértices, chamada relação de adjacência. Especificamente, dois vértices x e y são adjacentes, se {x, y} for uma aresta. Um gráfico pode ser totalmente especificado pela sua matriz adjacente A, que é um n × n {\\i1}displaystyle n\i}
matriz quadrada, com Aij especificando o número de ligações do vértice i ao vértice j. Para um gráfico simples, A i j ∈ {0 , 1 } {\posições ao estilo A_{ij} in {0,1}}
, indicando respectivamente a desconexão ou ligação, enquanto que A i i = 0 {\i1}displaystyle A_{ii}=0}
(isto é, uma borda não pode começar e terminar no mesmo vértice). Os gráficos com autolops serão caracterizados por alguns ou todos ao estilo A i i {\\i}{ii}}.
sendo igual a um inteiro positivo, e os multigrafos (com múltiplas arestas entre os vértices) serão caracterizados por alguns ou todos os A i j {\i}{ij}}
sendo igual a um número inteiro positivo. Os gráficos não direccionados terão uma matriz de adjacência simétrica ( A i j = A j i {\displaystyle A_{ij}=A_{ji}}}
).
GraphEdit dirigido
Um gráfico dirigido ou digráfico é um gráfico em que as arestas têm orientações.
Num sentido restrito mas muito comum do termo, um gráfico dirigido é um par G = ( V , E ) {\displaystyle G=(V,E)}
compreendendo:
- V {\i}displaystyle V
, um conjunto de vértices (também chamados nós ou pontos);
- E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 e x ≠ y } Esubseteq (x,y)mid (x,y)in V^{2};xtextrm (e)xneq y
, um conjunto de arestas (também chamadas arestas direccionadas, links direccionados, linhas direccionadas, setas ou arcos) que são pares ordenados de vértices (ou seja, uma aresta está associada a dois vértices distintos).
Para evitar ambiguidade, este tipo de objecto pode ser chamado precisamente um gráfico simples dirigido.
Na aresta ( x , y ) {\displaystyle (x,y)}
dirigido de x {\displaystyle x}
a y {\displaystyle y}
, os vértices x {\displaystyle x}
e y {\displaystyle y}
são chamados os pontos finais da borda, x {\displaystyle x}
a cauda da borda e y {\displaystyle y}
a cabeça da borda. Diz-se que a borda une x {\displaystyle x}
e y {\displaystyle y}
e para ser incidente em x {\displaystyle x}
e em y {\displaystyle y}
. Pode existir um vértice num gráfico e não pertencer a uma aresta. A aresta ( y , x ) {\\i1} ao estilo de um ecrã (y,x)}
é chamada a aresta invertida de ( x , y ) {\i} {\i1}displaystyle (x,y)}
. As arestas múltiplas, não permitidas pela definição acima, são duas ou mais arestas com a mesma cauda e a mesma cabeça.
Num sentido mais geral do termo permitindo múltiplas arestas, um gráfico dirigido é um triplo ordenado G = ( V , E , ϕ ) {\displaystyle G=(V,E,\phi )}
compreendendo:
- V {\i}displaystyle V
, um conjunto de vértices (também chamados nós ou pontos);
- E {\i1}displaystyle E
, um conjunto de arestas (também chamadas arestas direcionadas, links direcionados, linhas direcionadas, setas ou arcos);
- ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 e x ≠ y } estilo de jogophi :E para o meio (x,y)em V^{2};xtextrm;xneq y
, uma função de incidência mapeando cada aresta a um par de vértices ordenados (ou seja, uma aresta está associada a dois vértices distintos).
Para evitar ambiguidade, este tipo de objecto pode ser chamado precisamente um multigrafo dirigido.
Um laço é uma aresta que une um vértice a si mesma. Os gráficos dirigidos, tal como definidos nas duas definições acima, não podem ter loops, porque um loop que une um vértice x {\displaystyle x}
é a borda (para um gráfico simples dirigido) ou é incidente sobre (para um multigrafo dirigido) ( x , x ) {\displaystyle (x,x)}
que não está em { ( x , y ) ∣ ( x , y ) ∈ V 2 e x ≠ y } estilo de jogo (x,y)mid (x,y)in V^{2};xtextrm
/div> . Assim, para permitir loops, as definições devem ser expandidas. Para os gráficos simples dirigidos, a definição de E {\i1}displaystyle E}
deve ser modificado para E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } Esubseteq (x,y)mid (x,y)in V^{2}}displaystyle
. Para os multigrafos dirigidos, a definição de ϕ {\i1}displaystyle {\i}
deve ser modificado para ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } estilo de jogophi :E para o meio (x,y)em V^{2}}.
. Para evitar ambiguidade, estes tipos de objectos podem ser chamados precisamente um gráfico simples dirigido que permite loops e um multigráfico dirigido que permite loops (ou uma aljava), respectivamente.
As bordas de um gráfico simples dirigido que permite loops G {\displaystyle G}.
é uma relação homogénea ~ nos vértices de G {\displaystyle G}
que se chama a relação de adjacência de G {\displaystyle G}
. Especificamente, para cada borda ( x , y ) {\displaystyle (x,y)}
, os seus pontos finais x {\displaystyle x}
e y {\displaystyle y}
~ y {\displaystyle y}
Gráfico mistoEditar
Artigo principal: Gráfico mistoUm gráfico misto é um gráfico em que algumas arestas podem ser dirigidas e algumas podem não ser direccionadas. É um triplo ordenado G = (V, E, A) para um gráfico simples misto e G = (V, E, A, ϕE, ϕA) para um multigráfico misto com V, E (as arestas não direccionadas), A (as arestas direccionadas), ϕE e ϕA definidos como acima. Os gráficos dirigidos e não dirigidos são casos especiais.
GraphEdit
Um gráfico ponderado com dez vértices e doze arestas.Um gráfico ponderado ou uma rede é um gráfico no qual um número (o peso) é atribuído a cada aresta. Tais pesos podem representar, por exemplo, custos, comprimentos ou capacidades, dependendo do problema em questão. Tais gráficos surgem em muitos contextos, por exemplo, em problemas de percurso mais curto, como o problema do caixeiro-viajante.
