Algumas Definições
Caminho (walk): um caminho de um vértice Vi para um vértice Vj é uma
sequencia alternada de vértice e arestas adjacentes do grupa G.
Caminho fechado (clased walk): caminho que começa e termina no mesmo
vértice.
Trajeto (path): caminho de Vi pra Vj sem arestas repetidas.
Trajeto simples (simple path): caminho de Vi pra Vj sem arestas
e vértices
repetidos.
Circuito (circuit): Trajeto fechado isto é, um caminho onde não há arestas
repetidas e os vértices inicial e final são indenticos Vi = Vj.
Circuito simples (simple circuit): trajeto fechado, isto é, um caminho onde
não há arestas nem vértice repetidos exatos ou vértice inicial e final são idênticos.
Síntese
Tipo
Aresta
Repetida
Vértice
Repetido
Caminho (walk)
Pode
Pode
Começa e
termina no
mesmo vértice
Pode
Caminho fechado (closed walk)
Pode
Pode
Sim
Trajeto (path)
Não
Pode
Pode
Trajeto Simples (simple path)
Não
Não
Não
Circuito (circuit)
Não
Pode
Sim
Circuito simples (circuit simple)
Não
Vi = Vj
sim

O numero de arestas que incidisse sobre um vértice V é chamado “grau de
V”.

Um grafo é conexo se existir um caminho entre quaisquer dois vértices de
G.
Grafo regular: todos os vértices têm o mesmo grau.

Fundamentos
Um grafo G consiste de dois tipos de elementos, ou seja, vértices e arestas que se disse
para ligar o par de vértices. O conjunto de arestas é geralmente definida como um conjunto de
subconjuntos de dois elementos do conjunto de vértices.
Bordas podem ser dotada de sentido, levando à noção de um grafo dirigido ou dígrafo , veja a
Seção Direção .
Modelos alternativos de gráfico existe, por exemplo, um gráfico pode ser pensado como
um Boolean função binária sobre o conjunto de vértices ou como um quadrado (0,1) - matriz .
Um vértice (elemento básico) é simplesmente desenhado como um nó ou
um ponto. O conjunto de vértices de G é denotado por V (G), ou V, quando não há perigo de
confusão. A ordem de um grafo é o número dos seus vértices, ou seja, | V (G) |.
Uma aresta (um conjunto de dois elementos) é desenhada como uma linha conectando dois
vértices, endvertices chamado, ou pontos de extremidade. Uma aresta com
endvertices X e Y é denotado por xy sem mid-ponto entre eles, isto é, não
escrever x ⋅ y. O conjunto de arestas de G é denotado por E (G), ou E quando não há perigo
de confusão.
O tamanho de um grafo é o número de suas arestas, ou seja, | E (G) |.
Um laço é uma aresta cuja endvertices são o mesmo vértice;. Uma aresta é múltiplo, caso
exista outra borda com a mesma endvertices caso contrário, é simples;. A multiplicidade de
uma aresta é o número de arestas múltiplas partilha a mesma endvertices a multiplicidade de
um gráfico, a multiplicidade máximo de suas bordas. Um grafo é um grafo simples se não
tem arestas múltiplas ou loops, um multigrafo se ele tem várias arestas, mas sem alças, e
um pseudograph se ele contém várias arestas e loops. Quando afirmar, sem qualquer
qualificação, um gráfico é quase sempre considerado simples.
Um rótulo pode ser usado em qualquer uma borda ou um vértice, quer identificar-lo ou indicar
o significado. Gráficos com beiradas ou vértices são conhecidos como marcado, aqueles sem
a unlabeled. Mais especificamente, os gráficos com os vértices são rotulados apenas vértice
marcado, aqueles com beiradas são apenas ponta
rotulados.
O gráfico de exemplo na figura à direita é um grafo simples
com conjunto de vértices V = {1, 2, 3, 4, 5, 6} e conjunto de
arestas E = {{1,2}, {1,5}, {2, 3}, {2,5}, {3,4}, {4,5}, {4,6}} (com
o w mapa sendo a identidade).
A hyperedge é uma vantagem que é permitido levar em qualquer número de vértices, mesmo
2 ou mais. Um gráfico que permite que qualquer hyperedge é chamado de hipergrafos . Um
gráfico simples, pode ser considerada um caso especial do hipergrafo, ou seja, o 2-uniforme
hipergrafo. Entretanto, quando declarou, sem qualquer qualificação, uma vantagem é sempre
assumida a ser composta de no máximo 2 vértices, e um gráfico nunca é confundido com um
hipergrafo.
O complemento \ bar {G} <math> <math> de um grafo G é um grafo com o mesmo conjunto
de vértices G, mas com um conjunto de arestas xy que essa é uma vantagem no bar \ <math>
{G} </ math> se e somente se xy não é uma aresta em G.
Um grafo é um grafo vazio, possivelmente com alguns vértices, mas sem arestas.
O grafo nulo é o grafo sem vértices e sem arestas.
Um grafo é infinito se ele tem muitos vértices inifinitely ou bordas ou ambos, o grafo
é finito. Caso contrário, quando afirmou sem qualquer qualificação, um gráfico é geralmente
assumida como ser finito.
Dois grafos G e H são ditos isomorfos, denotado por G ~ H, se houver um-para-um
correpondence um, chamado de isomorfismo entre os vértices do grafo tal que dois vértices
são adjacentes em G se e somente se sua vértices correspondentes são adjacentes em H. Da
mesma forma, um grafo G é dito ser homomórfica para um gráfico de H se existe um
mapeamento, chamado homomorfismo , a partir de V (G) a V (H) tal que, se dois vértices são
adjacentes em G, então seus vértices correspondentes são adjacentes em H.
Subgrafo
Um subgrafo de um grafo G é um grafo cujos vértices e borda conjuntos são subconjuntos
de G. Pelo contrário, um supergraph de um grafo G é um grafo que contém G como um
subgrafo. Dizemos que um grafo G contém um outro gráfico H se algum subgrafo de G é
isomorfo a H.
Um subgrafo H é um grafo parcial, ou factor, de um grafo G se ela tem o mesmo conjunto de
vértices G. Dizemos vãos G H.
Um subgrafo H de um grafo G é dito ser induzido se, para qualquer par de vértices x e y de
H, xy é uma aresta de H se e somente se xyé uma aresta de G. Em outras palavras, H é um
induzida subgrafo de G se ela tem mais arestas que aparecem em G sobre o conjunto mesmo
vértice. Se H é escolhido com base em um subconjunto S de vértices de V (G), então H pode
ser escrito como G [S] e está a ser dito induzida por S.
Um grafo que não contém H como um subgrafo induzido é dito ser H-livre.
Um gráfico universal em uma classe de gráficos de K é um grafo simples em que cada
elemento de K pode ser incorporado como um subgrafo.
Caminho
Tradicionalmente, um caminho gráfico é composto de uma seqüência de arestas incidentes
sucessivamente e seus endvertices, onde os vértices são distintos encerra. Na literatura
moderna, esta definição geralmente se refere ao que é conhecido como
uma fuga, a pé ouaberto. Ao afirmar, sem qualquer qualificação , um caminho de n vértices,
denotado por P n, é geralmente assumida como um caminho simples, ou uma pista
simples, no sentido moderno, ou seja, cada vértice é incidente a, no máximo, duas bordas.
Dois caminhos são internamente disjuntos (algumas pessoas consideram independentes) se
não tiverem nenhum vértice em comum, exceto o último e os primeiros.
O comprimento de um caminho é o número de arestas que o caminho usa P. Comprimento n tem n 1. Algumas pessoas contam arestas múltiplas múltiplas vezes é. No
exemplo do gráfico, (1, 2, 5, 1, 2, 3) um caminho com comprimento 5, e (5, 2, 1) é um caminho
simples de comprimento 2.
Um caminho que abrangem também é chamado um caminho Hamiltoniano , ou o caminho
rastreáveis;. Um gráfico que contém um caminho hamiltoniano é rastreável um gráfico e que,
dado qualquer par de (distintos) vértices, contém um caminho hamiltoniano usá-los como
endvertices, um Hamiltoniano ligado gráfico.
Ciclo
Tradicionalmente, um ciclo em um grafo consiste de uma seqüência de arestas incidentes
sucessivamente e seus endvertices, onde os vértices de terminação são idênticos. Na literatura
moderna, esta definição geralmente se refere ao que é conhecido como
umcircuito fechado ou a pé. Quando afirma, sem qualquer qualificação,
um ciclo de n vértices, denotado por C n, é geralmente considerado um ciclo simples, ou
um circuito simples, no sentido moderno, ou seja, cada vértice é incidente a exatamente duas
arestas. No gráfico acima (1, 5, 2, 1) é um ciclo simples.
O comprimento de um ciclo é o número de suas bordas. N C tem comprimento n. Um ciclo,
ao contrário de um caminho, não é permitido ter comprimento 0. Ciclos de comprimento 1 são
laços. Ciclos de comprimento 2 são pares de arestas múltiplas. No gráfico de exemplo, (1, 2, 3,
4, 5, 2, 1) é um ciclo de comprimento 6.
Um ciclo que tem comprimento ímpar é um ciclo ímpar, é um mesmo ciclo. Contrário gráfico
pode ser provado bipartido se não existem não qualquer estranho. Ciclo, Veja grafo bipartido
completo
O perímetro de um grafo é o comprimento de um simples curto) ciclo (no gráfico,
a circunferência, o comprimento de uma (longa) ciclo. simples, o perímetro ea circunferência
de um grafo acíclico é definida para ser infinito ∞.
Um grafo é acíclico se não contém ciclos; unicyclic se contém exatamente um ciclo,
e pancyclic se ele contém todos os ciclos de tempo possível (de 3 a ordem do gráfico).
Um caminho euleriano em um grafo é um caminho que usa cada aresta exatamente uma vez.
Se tal caminho existe, o gráfico é chamado de travessia. Um ciclo euleriano é um ciclo que
usa cada aresta exatamente uma vez.
O grafo do exemplo não contém um caminho euleriano, mas contém um caminho hamiltoniano.
C 3 é chamado um triângulo.
Um ciclo que abrange também é chamado um ciclo hamiltoniano . Um gráfico que contém um
ciclo hamiltoniano é um grafo hamiltoniano.
Árvore
A árvore é um grafo conexo simples acíclico. Um vértice de grau 1 é chamado de
uma folha, ou pendente de vértice. Um incidente de borda de uma folha é uma borda da
folha, ou pendente de borda. (Algumas pessoas definem uma borda da folha, uma folha e
depois definir um vértice folha em cima dela. Estes dois conjuntos de definições são muitas
vezes utilizados indiferenciadamente.) A folha vértice não é um vértice interno. Às vezes, um
vértice da árvore é distinto e chamado de raiz. Uma árvore de raízes é uma árvore com uma
raiz. árvores enraizadas muitas vezes são tratados como grafos acíclicos dirigidos com as
bordas apontando para longe da raiz.
Árvores são comumente usadas como estruturas de dados em ciência da computação
(veja estrutura de dados árvore ).
Uma floresta é uma união disjunta-vértice de árvores, ou, equivalentemente, um grafo acíclico.
A subárvore do grafo G é um subgrafo que é uma árvore.
Uma árvore geradora é um grafo parcial que é uma árvore. Cada gráfico tem uma floresta
geradora. Mas só ligado um gráfico tem uma árvore geradora.
Um tipo especial de árvore é chamado de estrela de K 1, K. Induzida Uma estrela com 3 arestas
é uma garra.
Uma árvore k-ária é uma árvore enraizada no qual cada vértice interno tem filhos k. An-1 Ary
árvore é apenas um caminho. A-2 Ary árvore também é chamada de árvore binária.
Panelinha
O grafo completo K n de ordem n é um grafo simples com n vértices em que cada vértice é
adjacente a todos os outros. O grafo do exemplo não está completo. O gráfico completo
sobre n vértices é frequentemente denotado por K n. Ele tem n (n -1) / 2 arestas
(correspondendo a todas as possíveis escolhas de pares de vértices).
A camarilha (pronuncia-se "do clique) em um grafo é um conjunto de pares de vértices
adjacentes. Uma vez que qualquer subgrafo induzido por um clique é um subgrafo completo,
os dois termos e suas notações são geralmente usados alternadamente. camarilha Ak é um
grupinho de k ordem. No grafo de exemplo acima, os vértices 1, 2 e 5 formam um 3-clique, ou
um triângulo.
A camarilha do número ω (G) de um grafo G é o fim de uma maior clique no G.
Adjacência e grau
Na teoria dos grafos, grau, especialmente a de um vértice, é geralmente uma medida de
adjacência imediata.
Uma aresta conecta dois vértices; esses dois vértices são ditos incidentes à margem, ou,
equivalentemente, que o incidente de ponta para os dois vértices de incidência. Graus
relacionadas Todos os conceitos têm a ver com adajacency ou.
O grau ou valência, d G (v) de um vértice v em um grafo G é o número de arestas
incidentes av, com loops contados duas vezes. Um vértice de grau 0 é um vértice isolado. Um
vértice de grau 1 é uma folha. No grafo de exemplo os vértices 1 e 3 têm um grau de 2, 2,4 e 5
vértices possuem um grau de 3 eo vértice 6 tem um grau de 1. Se E é finito, então a soma total
dos graus dos vértices é igual a duas vezes o número de arestas.
Uma seqüência de grau é uma lista de graus de um grafo em ordem crescente de terceiros
(por exemplo d 1 d 2 ≥ ≥ ≥ d ... n). Uma seqüência de crescente inteiros não é viável se for uma
seqüência grau de algum gráfico.
Dois vértices u e v são considerados adjacentes se uma aresta existe entre eles. Denotamos
por ↓ v u. No gráfico acima, os vértices 1 e 2 são adjacentes, mas os vértices 2 e 4 não são. O
conjunto de vizinhos, chamado de ( aberto) vizinhança N G (v) por um vértice vem um
grafo G, composto por todos os vértices adjacentes a v, mas não
incluindo v. Quando v também está incluído, é chamado de umbairro fechado, denotado
por N G [v]. Ao afirmar, sem qualquer qualificação, um bairro é considerado aberto vizinhos. O
subscrito G é geralmente descartado quando não há perigo de: confusão. No exemplo do
gráfico, vértice 1 tem dois 2 e 5. vértices Para um grafo simples, o número de vizinhos que tem
um vértice coincide com o seu grau.
Um conjunto de dominar um grafo é um subconjunto de vértices cuja fechado bairro incluir
todos os vértices do grafo. Um vértice vdomina outro vértice u se existe uma aresta
de v para u. Um subconjunto de vértices V domina outro subconjunto U vértice se cada vértice
em U é adjacente a algum vértice em V. O tamanho mínimo de um conjunto dominante é
a dominação número γ (G).
Nos computadores, um número finito, dirigidos ou não dirigidos gráfico (com n vértices, por
exemplo) é freqüentemente representado por sua matriz de adjacência : uma n-porn matriz cuja entrada na linha i e coluna j fornece o número de arestas do i-ésimo para o
vértice j-th.
Gráfico Teoria espectral estuda as relações entre as propriedades do gráfico e sua matriz de
adjacência.
O máximo grau Δ (G) de um grafo G é o maior grau de todos os vértices, o grau
mínimo δ (G), o menor.
Um gráfico em que cada vértice tem o mesmo grau é regular . É k-regular se todo vértice tem
grau k. A-regular gráfico 0 é um conjunto independente. A-regular gráfico 1 é um casamento. A2 é regular gráfico uma união disjunta de ciclos de vértice. A-regular gráfico 3 está a ser
dito cúbicos, ou trivalente.
Um fator k é um regular abrangendo subgrafo k. Um factor-1 é um casamento perfeito. Uma
partição de arestas de um grafo em k-fatores é chamada de k-fatoração. A-factorável
gráfico k é um grafo que admite uma k-fatoração.
Um grafo é biregular se tem um máximo de desigualdade e graus de mínima e cada vértice
tem um desses dois graus.
Um grafo fortemente regular é um grafo regular tal que qualquer par de vértices adjacentes
tenham o mesmo número de vizinhos comuns como outros pares adjacentes e que qualquer
vértice não adjacente têm o mesmo número de vizinhos comuns como outros pares
nonadajacent.
Independência
Na teoria dos grafos, a palavra independente normalmente carrega a conotação de disjuntos
dois a dois ou mutuamente não adjacentes.Nesse sentido, a independência é uma forma
de nonadjacency imediato. Um vértice isolado não é um vértice incidente a todas as bordas.
Um conjunto independente, ou um conjunto estável ou , é um conjunto de isolados.
vértices staset Desde o gráfico induzido por qualquer conjunto independente é um gráfico
vazio, os dois termos são geralmente usados alternadamente;. No exemplo acima, os vértices
1, 3 e 6 forma um conjunto independente e 3, 5 e 6 forma uma outra.
A independência número α (G) de um grafo G é o tamanho de um maior conjunto
independente de G.
Um gráfico pode ser decomposto em conjuntos independentes no sentido de que o vértice de
todo o conjunto do gráfico pode ser particionado em subconjuntos disjuntos pares
independentes. Tais subconjuntos independentes são chamados de conjuntos partite, ou
simplesmente peças.
Um gráfico que pode ser decomposto em dois conjuntos partite, mas não menos
é bipartido, três sets, mas não menos, tripartite; kconjuntos, mas não menos, k-partite, um
número desconhecido de jogos, multipartite. E An-partite gráfico 1 é o mesmo como um
conjunto independente, ou um gráfico vazio. 2-partite Um gráfico é o mesmo que um grafo
bipartido. Um gráfico que pode ser decomposto em conjuntos partite k é dito igualmente ser kilusório .
Um grafo completo é multipartite um gráfico no qual os vértices são adjacentes se e somente
se eles pertencem a conjuntos diferentes partite. Um grafo bipartido completo é também
referido como um biclique.
Um grafo-partite k é semiregular se cada um de seu conjunto partite tem um grau
uniforme; equipartite se cada conjunto partite tem o mesmo tamanho e equilibrada k partitese cada conjunto partite difere em tamanho, no máximo, 1 com qualquer outra.
O número correspondente α (G) de um grafo G é o tamanho de uma
maior harmonização, ou pares arestas disjuntas vértice de G.
A correspondência abrange, também chamado de um casamento perfeito é um casamento
que cobre todos os vértices de um grafo.
Conectividade
Conectividade alarga o conceito de adjacência e é essencialmente uma forma (e medida)
de adjacência concatenadas.
Se é possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um
grafo, o grafo é dito ser ligado, caso contrário, o gráfico é desconectado vértices. Um grafo
é totalmente desconectado se não há caminho de ligar qualquer par de asas. Este é apenas
outro nome para descrever um gráfico vazio ou um conjunto independente.
Um vértice de corte, ou ponto de articulação, é um vértice cuja remoção desliga um grafo.
Um conjunto de corte, ou corte de vérticesou separação definida, é um conjunto de vértices
cuja remoção desliga o gráfico.
Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro,
mesmo depois de remover qualquer k - vértices, então o grafo é dito ser k-conexo. 1 Note que
um grafo é k-conexo se e somente se ele contiver k internamente disjuntos caminhos entre
quaisquer dois vértices. O grafo do exemplo acima é conectado (e, portanto, um conectado),
mas não 2-conectados. Aconectividade κ (G) de um grafo G é o número de vértices Mínimo
necessário para desligar G. Por convenção, n K tem conectividade n- 1, e um grafo
desconectado tem conectividade 0.
Uma ponte, ou a borda de corte ou istmo é uma aresta cuja remoção desliga um grafo. (Por
exemplo, uma árvore é feita inteiramente de pontes.) Um conjunto de desconexão é um
conjunto de arestas cuja remoção aumenta o número de componentes. Um corte de borda é o
conjunto de todas as bordas com um endvertex em alguns adequada vértice subconjunto S e
outro endvertex em V (G) \ Sdesconectar. margens de 3 K forma um conjunto de desligar, mas
não a borda de um conjunto de corte. Quaisquer duas arestas de K,de 3 de formar um conjunto
mínimo de desligar, assim como um; borda. cortados Uma aresta de corte é necessariamente
uma e desconectar um conjunto mínimo de um grafo não vazio é necessariamente um corte de
ponta. Um título é um mínimo (mas não necessariamente o mínimo), nonempty conjunto de
arestas cuja remoção desliga um grafo.
Um grafo é k-aresta-conexo se qualquer subgrafo formado através da remoção de
qualquer k - arestas ainda está conectado. Κ 1 Aconectividade EDGE (G) de um grafo G é o
número de arestas Mínimo necessário para desligar G conhecido. Um bem- resultado é que
κ (G) ≤ κ (G) ≤ δ (G).
Um componente é um subgrafo conectado máximo, um por categoria, a 2-conectados
subgrafo máximo ou uma ponte com o seu endvertices e
uma componente de biconnected, um conjunto máximo de arestas em que quaisquer dois
membros estão em um ciclo simples comum.
Distância
A distância d G (u, v) entre os dois (não é necessário distintas) vértices u e v em um grafo G é
o comprimento de um caminho mais curto entre eles. Subscrito G normalmente é descartado
quando não há perigo de confusão. Quando u e V são identitcal, a sua distância é 0.
Quando uev são inacessíveis do outro, a distância é definida para ser infinito ∞.
A excentricidade ε G (v) de um vértice v em um grafo G é a distância máxima de v para
qualquer outro vértice;. Diâmetro do diam (G)de um grafo G é máximo a excentricidade de
todos os vértices em um grafo, eo raio rad (G), no mínimo. Quando há dois componentes
no G, diam (G) e rad (G) a ser definido ∞ infinito. trivialmente, diam (G) ≤ 2 rad (G). Vertices
com excentricidade máxima são chamadosvértice periférico. Vértices de excentricidade
mínima formam o centro. Uma árvore tem no máximo dois vértices centro.
O índice de Wiener de um vértice v em um grafo G, denotado por W G (v) é a soma das
distâncias entre V e todos os outros. Oíndice de Wiener de um grafo G, denotado por W
(G), é a soma das distâncias sobre todos os pares de vértices. indireta do
gráficoWiener Um polinômio é definido como sendo Σ q
d (u, v)
sobre todos os pares não-
ordenados de vértices u e v. Wiener e polinomial Wiener são de interesse especial para os
químicos matemática.
k
A k-ésima potência G de um grafo G é um supergraph formado pela adição de uma aresta
entre todos os pares de vértices de G, com distância de no máximo k. A segunda potência de
um gráfico é também chamado de quadrado.
A chave k é um grafo parcial em que cada dois vértices estão em k vezes mais tão distantes
no S do que em G. O número k é adilatação.-Chave k é usado para estudar a otimização da
rede geométrica.
Gênero
A travessia é um par de arestas de intersecção. Um grafo é embutido em uma superfície, se
seus vértices e arestas podem ser organizados sobre ele, sem qualquer cruzamento.
O gênero de um grafo é o menor gênero em toda a superfície em que o gráfico pode inserir.
Um grafo planar é aquele que pode ser extraída no euclidiana) plano (sem cruzamento, e
um gráfico de avião, uma que édesenhado de tal forma de gráfico. Em outras palavras, um
grafo planar é um grafo de gênero é de 0 a. exemplo planar, o grafo completo de n vertices,
para n> 4, não é planar gráfico. Além disso, uma árvore é necessariamente um planar.
Quando um gráfico é desenhado sem qualquer passagem, qualquer ciclo que envolve uma
região sem qualquer aresta que vão desde o ciclo dentro de formas região como um rosto. As
duas faces de um grafo plano são adjacentes se eles compartilham uma aresta comum.
*
A dupla, ou planar dupla quando o contexto deve ser clarificado, G de um grafo plano G é um
grafo cujos vértices representam as faces, incluindo qualquer outerface, de G e são adjacentes
*
em G se e somente se suas faces correspondentes são adjacentes emG. A dual de um grafo
planar é sempre uma pseudograph planar (por exemplo, considerar a dupla de um
triângulo). No caso familiar de um 3-articulado de forma simples planar grafo G (isomorfo a um
*
poliedro convexo P), o G dupla é também um articulado de forma simples planar graph-3 (e
isomorfo ao poliedro dual P
*).
Além disso, como podemos estabelecer um sentido de "dentro" e "fora" em um avião, podemos
identificar uma ultraperiféricas "região" que contém o gráfico inteiro, se o gráfico não cobrem
todo o plano. Região ultraperiférica é chamada de exterior face;. outerplanar Umgrafo é um
que pode ser sacado em planar a tal forma que seus vértices são adjacentes ao exterior do
rosto e um gráfico outerplane,aquele que é desenhado de tal forma.
O número mínimo de passagens que devem aparecer quando um gráfico é desenhado em um
plano é chamado o número de passagem.
O número mínimo de grafos planares necessários para cobrir um gráfico é a espessura do
gráfico.
Peso
Um grafo ponderado associa um número real da etiqueta (peso), com cada aresta no grafo.
O peso de um caminho em um grafo ponderado é a soma dos pesos das arestas
atravessadas. Às vezes o custo palavra é usada em vez do peso. Quando declarou sem
qualquer qualificação, um grafo é sempre assumiu ser ponderadas.
Direção
Um, ou dirigido borda do arco, é um par ordenado de endvertices;. Ordenados de tal par, o
primeiro vértice é chamado de cabeça, ouvértice inicial e um segundo,
um rabo, um terminal ou vértice. Pode ser pensado como vantagem associada a uma direção,
ou seja, que designa uma cabeça e uma cauda ao endvertices. Uma aresta não
direcionada ignora qualquer senso de direção e trata tanto endvertices alternadamente.
Um ciclo em um diágrafo, no entanto, mantém um senso de direção e trata tanto a cabeça ea
cauda idêntica. Um conjunto de arcos são múltiplas, ou em paralelo, se eles compartilham a
mesma cabeça eo rabo mesmo. Um par de arcos são anti-paralelas, se a cabeça / cauda é o
outro da cauda / cabeça. Um digrafo ou direcionado gráfico , é análogo a um grafo não
direcionado, exceto que contém pelo menos um arco. Um grafo orientado contém apenas os
arcos. Ao afirmar, sem qualquer qualificação, um gráfico é quase sempre considerado sem
direção. Além disso, um dígrafo é usualmente assumido que a ausência de arestas e sem
direção.
Um digrafo é chamado simples se não tem laços e, no máximo, um arco entre cada par de
vértices. Ao afirmar, sem qualquer qualificação, um dígrafo é supor geralmente para ser
simples.
Em um dígrafo Γ, podemos distinguir o grau fora d
+
Γ
(v), o número de arestas deixando um
-
vértice v, e em grau d Γ v), o número de arestas entrando em um vértice. V (O grau d Γ (v) de
um vértice v é igual à soma dos seus fora-e em graus. Quando o contexto é claro, o Γ subscrito
+
pode ser descartado. máximos e mínimos de graus lá fora são indicadas pela Δ (Γ) e δ
+ </ sub>
(Γ), máximo e mínimo e em graus, Δ - (Γ) e δ - </ sub> (Γ).
Um fora-bairro, ou conjunto de sucesso, N
+
Γ
(v) de um vértice v é o conjunto de coroa de
-.
arcos que vão de v Da mesma forma, umano bairro, ou conjunto antecessor, N Γ (v) de um
vértice v é o conjunto de chefes de arco entrar em v.
Uma fonte é um vértice com 0 em graus, e uma pia, 0 grau de saída.
Um vértice v domina outro vértice u se existe um arco de v para u;. Vértice Um
subconjunto S é a que domina, se não em cada vérticeS é dominado por alguns vértice
em S e em que domina, se cada vértice em S é dominado vértice não por alguns em S.
Um kernel é uma organização independente fora dominando conjunto. Um digrafo é kernel
perfeito se todos os sub induzida dígrafo tem um kernel.
Um digrafo Euleriano é um dígrafo com igual dentro e fora graus em cada vértice.
Uma orientação é uma atribuição de sentidos para as bordas de um ou parcialmente dirigido
grafo não direcionado. Ao afirmar, sem qualquer qualificação, geralmente é assumido que
todas as arestas sem direção são substituídos por um dirigido por uma orientação. Além disso,
o grafo subjacente é geralmente assumida ser indireta e simples.
Um torneio é um dígrafo em que cada par de vértices está ligado por exatamente um arco. Em
outras palavras, é um completo gráfico orientado.
Um caminho direcionado, ou apenas um caminho, quando o contexto é claro, é um caminho
simples orientada de modo que todos os arcos de ir na mesma direção, ou seja, todos os
vértices internos têm dentro e fora graus 1. Um vértice é alcançável a partir de outro
vértice u se há um caminho a que, a partir de U e termina em v. Note que a condição geral de
que u pode ser acessado a partir doacórdão, não implica que v também é acessível a partir
de u.
Um digrafo é fortemente conectado se cada vértice é alcançável a partir de todos os outros
seguindo as direções dos arcos. Pelo contrário, um diágrafo é fracamente ligado se o seu
grafo subjacente não direcionado é conectado. Um gráfico fracamente ligado pode ser pensado
como um dígrafo em que cada vértice é "alcançável" de todos os outros, mas não
necessariamente seguindo as direções dos arcos. Uma forte orientação é uma orientação que
produz um digrafo fortemente ligado.
Um ciclo dirigido, ou apenas um ciclo quando o contexto é claro, é um ciclo simples orientada
de modo que todos os arcos de ir na mesma direção, ou seja, todos os vértices têm dentro e
fora graus 1. Um digrafo é acíclico se não contém qualquer ciclo de instruções. A acíclicos,
dígrafo finito, sem vértices isolados, necessariamente, conter pelo menos uma fonte e pelo
menos uma pia.
Uma arborescência, ou fora de árvore ou ramificação, é uma árvore orientada na qual todos
os vértices são alcançáveis a partir de um único vértice. Da mesma forma, um em árvore é uma
árvore orientada em que um único vértice é alcançável a partir de todas as outras.
Vários
Uma invariante de gráfico é uma propriedade de um grafo G, muitas vezes um número, que
não dependem da ordenação dosvértices em G. Exemplos são gênero gráfico e fim gráfico .