Glossário de teoria dos grafos - Glossary of graph theory

Este é um glossário da teoria dos grafos . A teoria dos grafos é o estudo de grafos , sistemas de nós ou vértices conectados em pares por linhas ou arestas .

Símbolos

Colchetes []: $L [S]$ é a subgráfico induzida de um gráfico $G$ para vértice subconjunto $S$ .
Símbolo principal ': O símbolo primo é freqüentemente usado para modificar a notação para invariantes de gráfico de forma que se aplique ao gráfico de linha em vez do gráfico fornecido. Por exemplo, $α (G)$ é o número de independência de um gráfico; $α' (G)$ é o número correspondente do gráfico, que é igual ao número de independência de seu gráfico de linha. Da mesma forma, $χ (G)$ é o número cromático de um gráfico; $χ' (G)$ é o índice cromático do gráfico, que é igual ao número cromático de seu gráfico de linha.

UMA

absorvente: Um conjunto absorvente de um gráfico direcionado é um conjunto de vértices tal que, para qualquer vértice , há uma aresta de em direção a um vértice de . ${\ displaystyle A}$ ${\ displaystyle G}$ ${\ displaystyle v \ in G \ setminus A}$ ${\ displaystyle v}$ ${\ displaystyle A}$
acromático: O número acromático de um gráfico é o número máximo de cores em uma coloração completa.
acíclico: 1. Um gráfico é acíclico se não tiver ciclos. Um gráfico acíclico não direcionado é a mesma coisa que uma floresta . Os gráficos acíclicos direcionados são menos frequentemente chamados de gráficos direcionados acíclicos.; 2. Uma coloração acíclica de um gráfico não direcionado é uma coloração apropriada em que cada duas classes de cores induzem uma floresta.
matriz de adjacência: A matriz de adjacência de um gráfico é uma matriz cujas linhas e colunas são indexadas pelos vértices do gráfico, com um na célula para a linha $i$ e coluna $j$ quando os vértices $i$ e $j$ são adjacentes, e zero caso contrário.
adjacente: 1. A relação entre dois vértices que são extremos da mesma aresta.; 2. A relação entre duas arestas distintas que compartilham um vértice final.
α: Para um gráfico $G$ , $α (G)$ (usando a letra grega alfa) é seu número de independência (veja independente ), e $α' (G)$ é seu número correspondente (veja coincidência ).
alternando: Em um gráfico com correspondência, um caminho alternativo é um caminho cujas arestas alternam entre arestas correspondentes e não correspondentes. Um ciclo alternado é, da mesma forma, um ciclo cujas bordas alternam entre bordas combinadas e não combinadas. Um caminho de aumento é um caminho alternativo que começa e termina em vértices insaturados. Uma correspondência maior pode ser encontrada como a diferença simétrica da correspondência e do caminho de aumento; uma correspondência é máxima se e somente se não tiver um caminho de aumento.
anticadeia: Em um gráfico acíclico direcionado , um subconjunto $S$ de vértices que são incomparáveis aos pares, ou seja, para qualquer em $S$ , não há caminho direcionado de $x$ para $y$ ou de $y$ para $x$ . Inspirado na noção de antichains em conjuntos parcialmente ordenados . ${\ displaystyle x \ leq y}$
anti-gume: Sinônimo de não borda , um par de vértices não adjacentes.
anti-triângulo: Um conjunto independente de três vértices, o complemento de um triângulo.
ápice: 1. Um gráfico de vértice é um gráfico no qual um vértice pode ser removido, deixando um subgrafo plano. O vértice removido é chamado de ápice. Um grafo $k$ -apex é um grafo que pode ser tornado plano pela remoção de $k$ vértices.; 2. Sinônimo de vértice universal , um vértice adjacente a todos os outros vértices.
arborescência: Sinônimo para uma árvore enraizada e dirigida; veja a árvore .
arco: Veja a borda .
seta: Um par ordenado de vértices , como uma aresta em um gráfico direcionado . Uma seta $(x, y)$ tem uma cauda $x$ , uma cabeça $y$ e uma direção $de x para y$ ; $y$ é considerado o sucessor direto de $x$ e $x$ o predecessor direto de $y$ . A seta $(y, x)$ é a seta invertida da seta $(x, y)$ .
ponto de articulação: Um vértice em um grafo conectado cuja remoção desconectaria o grafo.
-ary: Uma árvore $k$ -ary é uma árvore enraizada na qual cada vértice interno não tem mais do que $k$ filhos. Uma árvore 1-ária é apenas um caminho. Uma árvore 2-ária também é chamada de árvore binária , embora esse termo se refira mais apropriadamente a árvores 2-árias nas quais os filhos de cada nó são distinguidos como filhos da esquerda ou da direita (com no máximo um de cada tipo). Uma árvore $k$ -ary é considerada completa se cada vértice interno tiver exatamente $k$ filhos.
aumentando: Um tipo especial de caminho alternativo; veja alternando .
automorfismo: Um automorfismo de gráfico é uma simetria de um gráfico, um isomorfismo do gráfico para si mesmo.

B

Bolsa: Um dos conjuntos de vértices em uma decomposição em árvore .
equilibrado: Um grafo bipartido ou multipartido é balanceado se cada dois subconjuntos de sua partição de vértice têm tamanhos dentro um do outro.
largura de banda: A largura de banda de um grafo $G$ é o mínimo, sobre todas as ordenações de vértices de $G$ , do comprimento da aresta mais longa (o número de passos na ordenação entre seus dois pontos finais). É também um a menos que o tamanho do clique máximo em um intervalo adequado de conclusão de $G$ , escolhido para minimizar o tamanho do clique.
biclique: Sinônimo para gráfico bipartido completo ou subgrafo bipartido completo; veja completo .
bicconectado: Normalmente um sinônimo para $2$ -vertex-conectado , mas às vezes inclui K _2, embora não seja 2-conectado. Veja conectado ; para componentes bicconectados , consulte componente .
número de ligação: A menor proporção possível entre o número de vizinhos de um subconjunto apropriado de vértices e o tamanho do subconjunto.
bipartido: Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos, de modo que os vértices de um conjunto não estão conectados entre si, mas podem ser conectados aos vértices do outro conjunto. Dito de outra forma, um gráfico bipartido é um gráfico sem ciclos ímpares; equivalentemente, é um gráfico que pode ser adequadamente colorido com duas cores. Grafos bipartidos são freqüentemente escritos $G = (U, V, E)$ onde $U$ e $V$ são os subconjuntos de vértices de cada cor. No entanto, a menos que o gráfico esteja conectado, ele pode não ter uma 2 coloração exclusiva.
biregular: Um gráfico biregular é um gráfico bipartido no qual existem apenas dois graus de vértice diferentes, um para cada conjunto da bipartição de vértice.
bloquear: 1. Um bloco de um gráfico $G$ é um subgráfico máximo que é um vértice isolado, uma borda de ponte ou um subgrafo de 2 conexões. Se um bloco é 2-conectado, cada par de vértices nele pertence a um ciclo comum. Cada aresta de um gráfico pertence a exatamente um bloco.; 2. O gráfico de blocos de um grafo $G$ é outro grafo cujos vértices são os blocos de $G$ , com uma aresta conectando dois vértices quando os blocos correspondentes compartilham um ponto de articulação; isto é, é o gráfico de intersecção dos blocos de $L$ . O gráfico de blocos de qualquer gráfico é uma floresta .; 3. O bloco de corte (ou bloco-ponto de corte) de um gráfico gráfico $G$ é um gráfico bipartido onde um conjunto partite consiste de cut-vértices de $L$ , e o outro tem um vértice para cada bloco de $L$ . Quando $G$ está conectado, seu gráfico de ponto de corte de bloco é uma árvore. ${\ displaystyle b_ {i}}$ ${\ displaystyle B_ {i}}$; 4. Um grafo de blocos (também chamado de árvore clique se conectado, e às vezes erroneamente chamado de árvore Husimi) é um grafo cujos blocos são grafos completos. Uma floresta é um gráfico de blocos; portanto, em particular, o gráfico de bloco de qualquer gráfico é um gráfico de bloco, e cada gráfico de bloco pode ser construído como o gráfico de bloco de um gráfico.
ligação: Um conjunto de corte mínimo : um conjunto de arestas cuja remoção desconecta o gráfico, para o qual nenhum subconjunto apropriado possui a mesma propriedade.
livro: 1. Um livro , gráfico de livro ou livro triangular é um gráfico tripartido completo $K 1,1, n$ ; uma coleção de $n$ triângulos unidos em uma borda compartilhada.; 2. Outro tipo de gráfico, também chamado de livro, ou livro quadrilátero, é uma coleção de $4$ ciclos unidos em uma borda compartilhada; o produto cartesiano de uma estrela com uma borda.; 3. A incorporação de um livro é a incorporação de um gráfico em um livro topológico, um espaço formado pela união de uma coleção de semiplanos ao longo de uma linha compartilhada. Normalmente, os vértices da incorporação precisam estar na linha, que é chamada de lombada da incorporação, e as bordas da incorporação precisam estar dentro de um único meio plano, uma das páginas do livro.
espinheiro: Uma amoreira - brava é uma coleção de subgráficos que se tocam mutuamente, onde dois subgráficos se tocam se compartilham um vértice ou cada um inclui um ponto final de uma aresta. A ordem de uma amora é o menor tamanho de um conjunto de vértices que tem uma interseção não vazia com todos os subgráficos. A largura da árvore de um gráfico é a ordem máxima de qualquer uma de suas amoreiras.
decomposição de ramo: A branch-decomposição de $G$ é um agrupamento hierárquico das bordas de $G$ , representados por uma árvore binária não enraizadas com suas folhas marcadas pelas bordas do $G$ . A largura da decomposição de um ramo é o máximo, sobre as arestas $e$ dessa árvore binária, do número de vértices compartilhados entre os subgráficos determinados pelas arestas de $G$ nas duas subárvores separadas por $e$ . O branchwidth de $L$ é a largura mínima de qualquer ramo de decomposição- $L$ .
largura de ramal: Veja decomposição de ramos .
Ponte: 1. Uma ponte , istmo ou borda cortada é uma borda cuja remoção desconectaria o gráfico. Um gráfico sem ponte é aquele que não tem pontes; equivalentemente, um gráfico conectado por 2 arestas.; 2. Especialmente no contexto de teste de planaridade , uma ponte de um ciclo é um subgrafo máximo que é separado do ciclo e no qual cada duas arestas pertencem a um caminho que é separado internamente do ciclo. Um acorde é uma ponte de uma borda. Um ciclo periférico é um ciclo com no máximo uma ponte; deve ser uma face em qualquer incorporação planar de seu gráfico.; 3. Uma ponte de um ciclo também pode significar um caminho que conecta dois vértices de um ciclo, mas é mais curto do que qualquer um dos caminhos no ciclo que conecta os mesmos dois vértices. Um gráfico em ponte é um gráfico no qual cada ciclo de quatro ou mais vértices tem uma ponte.
sem ponte: Um gráfico sem ponte é um gráfico que não possui arestas de ponte; isto é, um gráfico conectado por 2 arestas .
borboleta: 1. O gráfico borboleta possui cinco vértices e seis arestas; é formado por dois triângulos que compartilham um vértice.; 2. A rede borboleta é um gráfico usado como arquitetura de rede em computação distribuída, intimamente relacionado aos ciclos conectados a cubos .

C

C: $C n$ é um gráfico de ciclo de $n-$ vértices; veja o ciclo .
cacto: Um gráfico de cacto , árvore de cacto, cacto ou árvore Husimi é um gráfico conectado em que cada aresta pertence a no máximo um ciclo. Seus blocos são ciclos ou arestas simples. Se, além disso, cada vértice pertencer a no máximo dois blocos, então é chamado de cacto de Natal.
cela: Uma gaiola é um gráfico regular com a menor ordem possível para sua circunferência.
canônico
canonização: A forma canônica de um gráfico é uma invariante de forma que dois gráficos tenham invariantes iguais se e somente se eles forem isomórficos. As formas canônicas também podem ser chamadas de invariantes canônicos ou invariantes completos e, às vezes, são definidas apenas para os gráficos dentro de uma família particular de gráficos. A canonização de grafos é o processo de calcular uma forma canônica.
cartão: Um gráfico formado a partir de um dado gráfico, excluindo um vértice, especialmente no contexto da conjectura de reconstrução . Veja também baralho , o multiconjunto de todas as cartas de um gráfico.
largura de entalhe: A largura de entalhe é uma noção de largura de gráfico análoga à largura de ramificação, mas usando agrupamentos hierárquicos de vértices em vez de agrupamentos hierárquicos de arestas.
lagarta: Uma árvore ou lagarta é uma árvore em que os nós internos induzem um caminho.
Centro: O centro de um gráfico é o conjunto de vértices de excentricidade mínima .
cadeia: 1. Sinônimo de caminhada .; 2. Ao aplicar métodos de topologia algébrica a grafos, um elemento de um complexo de cadeia , ou seja, um conjunto de vértices ou um conjunto de arestas.
Cheeger constante: Veja expansão .
cereja: Uma cereja é um caminho em três vértices.
χ: $χ (G)$ (usando a letra grega chi) é o número cromático de $G$ e $χ' (G)$ é seu índice cromático; veja cromática e coloração .
filho: Em uma árvore com raiz, um filho de um vértice $v$ é vizinho de $v$ ao longo de uma aresta de saída, que está direcionada para longe da raiz.
acorde
cordal: 1. Uma corda de um ciclo é uma aresta que não pertence ao ciclo, para a qual ambos os pontos finais pertencem ao ciclo.; 2. Um gráfico de cordas é um gráfico em que cada ciclo de quatro ou mais vértices tem um acorde, então os únicos ciclos induzidos são triângulos.; 3. Um gráfico de acordes fortes é um gráfico de acordes em que cada ciclo de comprimento seis ou mais tem um acorde ímpar.; 4. Um grafo bipartido cordal não é cordal (a menos que seja uma floresta); é um grafo bipartido em que cada ciclo de seis ou mais vértices tem uma corda, então os únicos ciclos induzidos são 4 ciclos.; 5. A corda de um círculo é um segmento de linha que conecta dois pontos no círculo; o gráfico de interseção de uma coleção de acordes é chamado de gráfico circular .
cromático: Relacionado a coloração; veja a cor . A teoria dos grafos cromáticos é a teoria da coloração dos grafos. O número cromático $χ (G)$ é o número mínimo de cores necessárias em uma coloração adequada do $G$ . $χ'(G)$ é o índice cromático de $L$ , o número mínimo de cores necessárias numa adequada borda coloração de $L$ .
selecionável
capacidade de escolha: Um gráfico é $k$ -escolhível se tiver uma lista de cores sempre que cada vértice tiver uma lista de $k$ cores disponíveis. A escolha do gráfico é o menor $k$ para o qual ele pode ser $k$ -escolhível.
círculo: Um gráfico de círculo é o gráfico de interseção de cordas de um círculo.
o circuito: Um circuito pode se referir a uma trilha fechada ou a um elemento do espaço do ciclo (um subgrafo de abrangência Euleriana). A classificação do circuito de um gráfico é a dimensão do seu espaço de ciclo.
circunferência: A circunferência de um gráfico é a duração de seu ciclo simples mais longo. O gráfico é hamiltoniano se e somente se sua circunferência for igual a sua ordem.
classe: 1. Uma classe de gráficos ou família de gráficos é uma coleção (geralmente infinita) de gráficos, geralmente definida como os gráficos que possuem alguma propriedade específica. A palavra "classe" é usada em vez de "definir" porque, a menos que restrições especiais sejam feitas (como restringir os vértices a serem desenhados de um determinado conjunto e definir as arestas como conjuntos de dois vértices), classes de gráficos geralmente não são conjuntos quando formalizado usando a teoria dos conjuntos.; 2. Uma classe de cor de um gráfico colorido é o conjunto de vértices ou arestas com uma cor particular.; 3. No contexto do teorema de Vizing , na coloração de arestas de gráficos simples, um gráfico é considerado de classe um se seu índice cromático for igual a seu grau máximo, e de classe dois se seu índice cromático for igual a um mais o grau. De acordo com o teorema de Vizing, todos os gráficos simples são da classe um ou da classe dois.
garra: Uma garra é uma árvore com um vértice interno e três folhas, ou equivalentemente o grafo bipartido completo $K 1,3$ . Um gráfico livre de garras é um gráfico que não possui um subgráfico induzido que é uma garra.
clique: Um clique é um conjunto de vértices mutuamente adjacentes (ou o subgrafo completo induzido por esse conjunto). Às vezes, um clique é definido como um conjunto máximo de vértices mutuamente adjacentes (ou subgráfico completo máximo), um que não faz parte de nenhum conjunto maior (ou subgráfico). Um $k$ -clique é um clique de ordem $k$ . O número do clique $κ (G)$ de um grafo $G$ é a ordem de seu maior clique. Um gráfico de clique é um gráfico de interseção de cliques máximos. Veja também biclique , um subgrafo bipartido completo.
árvore de clique: Um sinônimo para um gráfico de blocos .
largura de clique: A largura de clique de um grafo $G$ é o número mínimo de rótulos distintos necessários para construir $G$ por operações que criam um vértice rotulado, formam a união disjunta de dois grafos rotulados, adicionam uma aresta conectando todos os pares de vértices com rótulos dados, ou reetiquetam todos os vértices com um determinado rótulo. Os gráficos de largura de clique no máximo $2$ são exatamente as cografias .
fechado: 1. Uma vizinhança fechada é aquela que inclui seu vértice central; ver vizinhança .; 2. Um passeio fechado é aquele que começa e termina no mesmo vértice; ver andar .; 3. Um gráfico é transitivamente fechado se for igual ao seu próprio fechamento transitivo; veja transitivo .; 4. Uma propriedade de gráfico é fechada em alguma operação em gráficos se, sempre que o argumento ou argumentos para a operação tiver a propriedade, o resultado também terá. Por exemplo, propriedades hereditárias são fechadas sob subgráficos induzidos; propriedades monótonas são fechadas em subgráficos; e propriedades menores fechadas são fechadas por menores.
fecho: 1. Para o fechamento transitivo de um gráfico direcionado, consulte transitivo .; 2. Um fechamento de um gráfico direcionado é um conjunto de vértices que não possuem arestas de saída para vértices fora do fechamento. Por exemplo, um sumidouro é um fechamento de um vértice. O problema de fechamento é o problema de encontrar um fechamento de peso mínimo ou máximo.
co-: Este prefixo tem vários significados geralmente envolvendo gráficos de complemento . Por exemplo, uma cografia é um gráfico produzido por operações que incluem complementação; um cocoloring é uma coloração em que cada vértice induz um conjunto independente (como na coloração própria) ou um clique (como na coloração do complemento).
cor
coloração: 1. Uma coloração de gráfico é uma rotulação dos vértices de um gráfico por elementos de um determinado conjunto de cores, ou equivalentemente, uma partição dos vértices em subconjuntos, chamados de "classes de cores", cada um dos quais está associado a uma das cores.; 2. Alguns autores usam "coloração", sem ressalvas, para significar uma coloração adequada, que atribui cores diferentes aos pontos finais de cada aresta. Na coloração de gráfico, o objetivo é encontrar uma coloração adequada que use o mínimo de cores possível; por exemplo, os gráficos bipartidos são os gráficos que possuem colorações com apenas duas cores, e o teorema das quatro cores afirma que todo gráfico planar pode ser colorido com no máximo quatro cores. Diz- se que um gráfico tem cor $k$ se tiver sido (apropriadamente) colorido com $k$ cores e $k$ -colorível ou $k$ -cromático se isso for possível.; 3. Muitas variações de coloração foram estudados, incluindo borda colorir (coloração bordas de modo que não há duas bordas com a mesma participação endpoint uma cor), lista de coloração (coloração adequada com cada vértice restrito a um subconjunto das cores disponíveis), coloração acíclico (todo subgrafo de 2 cores é acíclico), co-coloração (cada classe de cor induz um conjunto independente ou um clique), coloração completa (cada duas classes de cor compartilham uma aresta) e coloração total (ambas as arestas e vértices são coloridos).; 4. O número de coloração de um gráfico é um mais a degenerescência . É assim chamado porque a aplicação de um algoritmo de coloração gananciosa a uma ordem de degeneração do gráfico usa no máximo essa quantidade de cores.
comparabilidade: Um gráfico não direcionado é um gráfico de comparabilidade se seus vértices são os elementos de um conjunto parcialmente ordenado e dois vértices são adjacentes quando são comparáveis na ordem parcial. Da mesma forma, um gráfico de comparabilidade é um gráfico que tem uma orientação transitiva. Muitas outras classes de gráficos podem ser definidas como gráficos de comparabilidade de tipos especiais de ordem parcial.
complemento: O gráfico de complemento de um gráfico simples $L$ é um outro gráfico no mesmo conjunto vértice como $L$ , com uma borda para cada dois vértices, que não são adjacentes em $L$ . ${\ displaystyle {\ bar {G}}}$
completo: 1. Um grafo completo é aquele em que cada dois vértices são adjacentes: todas as arestas que poderiam existir estão presentes. Um gráfico completo com $n$ vértices é freqüentemente denotado como $K n$ . Um grafo bipartido completo é aquele em que cada dois vértices em lados opostos da partição de vértices são adjacentes. Um grafo bipartido completo com $a$ vértices de um lado da partição e $b$ vértices do outro lado é freqüentemente denotado como $K a, b$ . A mesma terminologia e notação também foram estendidas para gráficos multipartidos completos , gráficos nos quais os vértices são divididos em mais de dois subconjuntos e cada par de vértices em subconjuntos diferentes são adjacentes; se o número de vértices nos subconjuntos são $um, b, c, ...$ então este gráfico é denotado $K um, b, c, ...$ .; 2. A conclusão de um dado gráfico é um supergrafo que possui alguma propriedade desejada. Por exemplo, uma conclusão de acordes é um supergrafo que é um gráfico de acordes.; 3. Uma combinação completa é sinônimo de combinação perfeita ; veja correspondência .; 4. Uma coloração completa é uma coloração apropriada em que cada par de cores é usado para os pontos finais de pelo menos uma aresta. Toda coloração com um número mínimo de cores é completa, mas podem existir colorações completas com maior número de cores. O número acromático de um gráfico é o número máximo de cores em uma coloração completa.; 5. Um invariante completo de um gráfico é sinônimo de forma canônica, um invariante que possui valores diferentes para gráficos não isomórficos.
componente: Um componente conectado de um gráfico é um subgráfico conectado máximo. O termo também é utilizado para subgráficos máximas ou subconjuntos de vértices de um gráfico que têm alguma ordem superior de conectividade, incluindo vértice de corte , componentes triconnected , e componentes fortemente ligados .
condensação: A condensação de um grafo orientado $G$ é um gráfico acíclico dirigido com um vértice para cada componente fortemente ligado de $L$ , e uma aresta de ligação de pares de componentes que contêm os dois pontos de extremidade de pelo menos uma aresta em $L$ .
cone: Um gráfico que contém um vértice universal .
conectar: Causa para estar conectado .
conectado: Um grafo conectado é aquele em que cada par de vértices forma os pontos finais de um caminho. Formas superiores de conectividade incluem forte ligação nos gráficos dirigidos (para cada dois vértices existem caminhos a partir de um para o outro em ambos os sentidos), $k$ -vertex-conectado gráficos (remoção de menos de $k$ vértices não é possível desligar o gráfico), e $k$ -Edge gráficos conectados (remover menos de $k$ arestas não pode desconectar o gráfico).
conversar: O gráfico inverso é sinônimo de gráfico transposto; veja transpor .
essencial: 1. Um $k$ -core é o subgrafo induzido formado pela remoção de todos os vértices de grau menor que $k$ , e todos os vértices cujo grau se torna menor que $k$ após remoções anteriores. Veja degeneração .; 2. Um núcleo é um grafo $G$ tal que todo homomorfismo de $G$ para si mesmo é um isomorfismo.; 3. O núcleo de um grafo $G$ é um grafo mínimo $H$ tal que existem homomorfismos de $G$ a $H$ e vice-versa. $H$ é exclusivo até isomorfismo. Pode ser representado como um subgrafo induzido de $G$ e é um núcleo no sentido de que todos os seus auto-homomorfismos são isomorfismos.; 4. Na teoria das correspondências de gráfico, o núcleo de um gráfico é um aspecto de sua decomposição Dulmage-Mendelsohn , formado como a união de todas as correspondências máximas.
cotree: 1. O complemento de uma árvore geradora .; 2. Uma estrutura de árvore enraizada usada para descrever uma cografia , em que cada vértice da cografia é uma folha da árvore, cada nó interno da árvore é rotulado com 0 ou 1, e dois vértices da cografia são adjacentes se e somente se seu menor comum ancestral na árvore é rotulado como 1.
cobrir: Uma cobertura de vértices é um conjunto de vértices incidentes em todas as arestas de um gráfico. Uma cobertura de aresta é um conjunto de arestas incidentes a cada vértice de um grafo. Um conjunto de subgráficos de um gráfico cobre aquele gráfico se sua união - considerada no vértice e na aresta - for igual ao gráfico.
crítico: Um gráfico crítico para uma determinada propriedade é um gráfico que possui a propriedade, mas de tal forma que todo subgrafo formado pela exclusão de um único vértice não possui a propriedade. Por exemplo, um gráfico de fator crítico é aquele que tem uma correspondência perfeita (um fator 1) para cada exclusão de vértice, mas (porque tem um número ímpar de vértices) não tem uma correspondência perfeita. Compare hypo- , usado para gráficos que não têm uma propriedade, mas para os quais cada deleção de um vértice tem.
cubo
cúbico: 1. Gráfico de cubo , o gráfico de oito vértices dos vértices e arestas de um cubo.; 2. Gráfico de hipercubo , uma generalização de dimensão superior do gráfico de cubo.; 3. Gráfico de cubo dobrado , formado a partir de um hipercubo, adicionando-se vértices opostos de conexão correspondentes.; 4. Gráfico de cubo dividido pela metade , o meio-quadrado de um gráfico de hipercubo.; 5. Cubo parcial , um subgrafo de um hipercubo que preserva a distância.; 6. O cubo de um gráfico $G$ é a potência do gráfico $G 3$ .; 7. Grafo cúbico , outro nome para um grafo regular de $3$ , em que cada vértice tem três arestas incidentes.; 8. Ciclos cúbicos conectados , um gráfico cúbico formado pela substituição de cada vértice de um hipercubo por um ciclo.
cortar
cut-set: Um corte é uma partição dos vértices de um gráfico em dois subconjuntos, ou o conjunto (também conhecido como conjunto de corte) de arestas que abrangem tal partição, se esse conjunto não estiver vazio. Diz-se que uma borda abrange a partição se tiver pontos de extremidade em ambos os subconjuntos. Assim, a remoção de um conjunto de corte de um gráfico conectado o desconecta.
ponto de corte: Veja o ponto de articulação .
cortar espaço: O espaço de corte de um gráfico é um GF (2) - espaço vetorial tendo o conjunto de corte s do gráfico como seus elementos e a diferença simétrica de conjuntos como sua operação de adição de vetor.
ciclo: Um ciclo pode se referir a uma caminhada fechada (também chamada de passeio ) ou, mais especificamente, a uma caminhada fechada sem vértices repetidos e, conseqüentemente, bordas (também chamada de ciclo simples). Em ambos os casos, a escolha do primeiro vértice geralmente é considerada sem importância: as permutações cíclicas da caminhada produzem o mesmo ciclo. Importantes casos especiais de ciclos incluem ciclos de Hamilton , ciclos induzidos , ciclos periféricas , e o ciclo mais curto, que define o perímetro de um gráfico. Um $k$ -ciclo é um ciclo de comprimento $k$ ; por exemplo, um $2-$ ciclo é um digon e um $3$ -ciclo é um triângulo. Um gráfico de ciclo é um gráfico que é um ciclo simples; um gráfico de ciclo com $n$ vértices é comumente denotado $C n$ . O espaço do ciclo é um espaço vetorial gerado por ciclos simples em um gráfico.

D

DAG: Abreviatura de gráfico acíclico direcionado , um gráfico direcionado sem nenhum ciclo direcionado.
área coberta: O multiconjunto de grafos formado a partir de um único grafo $G$ excluindo um único vértice de todas as maneiras possíveis, especialmente no contexto da conjectura de reconstrução . Um deck de borda é formado da mesma maneira, excluindo uma única borda de todas as maneiras possíveis. Os gráficos em um baralho também são chamados de cartas . Veja também crítico (gráficos que possuem uma propriedade que não é mantida por nenhuma carta) e hipo- (gráficos que não possuem uma propriedade que é mantida por todas as cartas).
decomposição: Veja decomposição em árvore , decomposição em caminho ou decomposição em ramos .
degenerar
degeneração: Um gráfico $k-$ degenerado é um gráfico não direcionado no qual todo subgrafo induzido tem grau mínimo no máximo $k$ . A degenerescência de um gráfico é o menor $k$ para o qual ele é $k-$ degenerado. Uma ordenação de degeneração é uma ordenação dos vértices de forma que cada vértice tenha um grau mínimo no subgrafo induzido dele e todos os vértices posteriores; em uma ordenação de degeneração de um grafo $k-$ degenerado, cada vértice tem no máximo $k$ vizinhos posteriores. A degenerescência também é conhecida como número $k$ -core, largura e ligação, e um mais a degenerescência também é chamada de número colorido ou número de Szekeres-Wilf. Os gráficos $k-$ degenerados também são chamados de gráficos $k-$ indutivos.
grau: 1. O grau de um vértice em um gráfico é o seu número de arestas incidentes. O grau de um gráfico $G$ (ou seu grau máximo) é o máximo dos graus de seus vértices, freqüentemente denotado por $Δ (G)$ ; o grau mínimo de $G$ é o mínimo de seus graus de vértice, freqüentemente denotado $δ (G)$ . O grau às vezes é chamado de valência ; o grau de $v$ em $G$ pode ser denotado $d G (v)$ , $d (G)$ ou $deg (v)$ . O grau total é a soma dos graus de todos os vértices; pelo lema do aperto de mão , é um número par. A sequência de graus é a coleção de graus de todos os vértices, em ordem classificada do maior para o menor. Em um gráfico direcionado, pode-se distinguir o grau de entrada (número de arestas de entrada) e o grau de saída (número de arestas de saída).; 2. O grau de homomorfismo de um grafo é sinônimo de seu número de Hadwiger , a ordem do maior clique menor.
Δ, δ: $Δ (G)$ (usando a letra grega delta) é o grau máximo de um vértice em $G$ , e $δ (G)$ é o grau mínimo; veja grau .
densidade: Em um gráfico de n nós, a densidade é a razão entre o número de arestas do grafo e o número de arestas de um grafo completo em n nós. Veja o gráfico denso .
profundidade: A profundidade de um nó em uma árvore com raiz é o número de arestas no caminho da raiz ao nó. Por exemplo, a profundidade da raiz é 0 e a profundidade de qualquer um de seus nós adjacentes é 1. É o nível de um nó menos um. Observe, no entanto, que alguns autores, em vez disso, usam profundidade como sinônimo para o nível de um nó.
diâmetro: O diâmetro de um gráfico conectado é o comprimento máximo do caminho mais curto . Ou seja, é o máximo das distâncias entre pares de vértices no gráfico. Se o gráfico tiver pesos em suas arestas, então seu diâmetro ponderado mede o comprimento do caminho pela soma dos pesos das arestas ao longo de um caminho, enquanto o diâmetro não ponderado mede o comprimento do caminho pelo número de arestas. Para gráficos desconectados, as definições variam: o diâmetro pode ser definido como infinito, ou como o maior diâmetro de um componente conectado, ou pode ser indefinido.
diamante: O gráfico do diamante é um gráfico não direcionado com quatro vértices e cinco arestas.
desconectado: Forte ly ligado . (Não deve ser confundido com desconectado )
digon: Um digon é um ciclo simples de comprimento dois em um gráfico direcionado ou multigrafo. Os digons não podem ocorrer em gráficos não direcionados simples, pois eles exigem a repetição da mesma aresta duas vezes, o que viola a definição de simples .
dígrafo: Sinônimo de gráfico direcionado .
dipata: Veja o caminho direcionado .
predecessor direto: A cauda de uma aresta direcionada cuja cabeça é o vértice dado.
sucessor direto: A cabeça de uma aresta dirigida cuja cauda é o vértice dado.
dirigido: Um grafo direcionado é aquele em que as arestas têm uma direção distinta, de um vértice para outro. Em um gráfico misto , uma aresta direcionada é novamente aquela que possui uma direção distinta; bordas direcionadas também podem ser chamadas de arcos ou setas.
arco dirigido: Veja a flecha .
borda direcionada: Veja a flecha .
linha dirigida: Veja a flecha .
caminho direcionado: Um caminho no qual todas as borda s têm o mesmo sentido . Se um caminho direcionado leva do vértice $x$ ao vértice $y$ , $x$ é o predecessor de $y$ , $y$ é o sucessor de $x$ e $y$ é considerado alcançável a partir de $x$ .
direção: 1. A relação assimétrica entre dois vértices adjacentes em um gráfico , representado por uma seta .; 2. A relação assimétrica entre dois vértices em um caminho direcionado .
desconectar: Causa para ser desconectado .
desconectado: Não conectado .
disjuntar: 1. Dois subgráficos são disjuntos de arestas se não compartilham arestas e disjuntos de vértices se não compartilham vértices.; 2. A união disjunta de dois ou mais gráficos é um grafo cujos conjuntos de vértices e arestas são as uniões disjuntas dos conjuntos correspondentes.
distância: A distância entre quaisquer dois vértices em um gráfico é o comprimento do caminho mais curto tendo os dois vértices como seus pontos finais.
domático: Uma partição domatic de um gráfico é uma partição dos vértices em conjuntos dominantes. O número domatic do gráfico é o número máximo de conjuntos dominantes em tal partição.
dominando: Um conjunto dominante é um conjunto de vértices que inclui ou é adjacente a cada vértice no gráfico; não deve ser confundido com uma cobertura de vértices, um conjunto de vértices que incide em todas as arestas do gráfico. Tipos especiais importantes de conjuntos dominantes incluem conjuntos dominantes independentes (conjuntos dominantes que também são conjuntos independentes) e conjuntos dominantes conectados (conjuntos dominantes que induziram subgráficos conectados). Um conjunto dominante de um único vértice também pode ser chamado de vértice universal. O número de dominação de um gráfico é o número de vértices no menor conjunto dominante.

E

E: $E (G)$ é o conjunto de arestas de $G$ ; veja o conjunto de bordas .
orelha: Uma orelha de gráfico é um caminho cujos pontos finais podem coincidir, mas no qual não há repetições de vértices ou arestas.
decomposição da orelha: Uma decomposição de orelha é uma partição das bordas de um gráfico em uma sequência de orelhas, cada uma das extremidades (após a primeira) pertencente a uma orelha anterior e cada um dos pontos internos não pertencendo a nenhuma orelha anterior. Uma orelha aberta é um caminho simples (uma orelha sem vértices repetidos), e uma decomposição de orelha aberta é uma decomposição de orelha em que cada orelha após a primeira é aberta; um gráfico tem uma decomposição em orelha aberta se, e somente se, for bicconectado. Uma orelha é ímpar se tiver um número ímpar de arestas, e uma decomposição de orelha ímpar é uma decomposição de orelha em que cada orelha é ímpar; um gráfico tem uma decomposição de orelha ímpar se e somente se for fator crítico.
excentricidade: A excentricidade de um vértice é a maior distância dele a qualquer outro vértice.
borda: Uma aresta é (junto com os vértices) uma das duas unidades básicas com as quais os gráficos são construídos. Cada aresta tem dois (ou em hipergrafos, mais) vértices aos quais está anexada, chamados de seus pontos finais. As bordas podem ser direcionadas ou não; arestas não direcionadas também são chamadas de linhas e arestas direcionadas também são chamadas de arcos ou setas. Em um gráfico simples não direcionado , uma aresta pode ser representada como o conjunto de seus vértices e, em um gráfico simples direcionado, pode ser representada como um par ordenado de seus vértices. Uma aresta que conecta os vértices $x$ e $y$ às vezes é escrita como $xy$ .
corte de borda: Um conjunto de arestas s cuja remoção desconecta o gráfico . Um corte de uma borda é chamado de ponte , istmo ou borda de corte .
conjunto de borda: O conjunto de arestas de um dado grafo $G$ , às vezes denotado por $E (G)$ .
gráfico sem bordas: O grafo sem arestas ou grafo totalmente desconectado em um determinado conjunto de vértices é o grafo que não tem arestas. Às vezes é chamado de gráfico vazio, mas esse termo também pode se referir a um gráfico sem vértices.
incorporação: Uma incorporação de gráfico é uma representação topológica de um gráfico como um subconjunto de um espaço topológico com cada vértice representado como um ponto, cada aresta representada como uma curva tendo as extremidades da aresta como extremidades da curva, e sem outras interseções entre vértices ou arestas. Um gráfico planar é um gráfico que possui tal incorporação no plano euclidiano, e um gráfico toroidal é um gráfico que possui tal incorporação em um toro. O gênero de um gráfico é o gênero mínimo possível de uma variedade bidimensional em que ele pode ser incorporado.
gráfico vazio: 1. Um gráfico sem bordas em um conjunto não vazio de vértices.; 2. O gráfico de ordem zero , um gráfico sem vértices e sem arestas.
fim: Um final de um gráfico infinito é uma classe de equivalência de raios, onde dois raios são equivalentes se houver um terceiro raio que inclui infinitos vértices de ambos.
ponto final: Um dos dois vértices unidos por uma determinada aresta, ou um do primeiro ou último vértice de um passeio, trilha ou caminho. O primeiro ponto final de uma determinada aresta direcionada é chamado de cauda e o segundo ponto final é chamado de cabeça .
enumeração: A enumeração de gráficos é o problema de contar os gráficos em uma determinada classe de gráficos, em função de sua ordem. De maneira mais geral, os problemas de enumeração podem se referir a problemas de contagem de uma certa classe de objetos combinatórios (como cliques, conjuntos independentes, colorações ou árvores geradoras) ou de listar algoritmicamente todos esses objetos.
Euleriana: Um caminho Euleriano é uma caminhada que usa cada borda de um gráfico exatamente uma vez. Um circuito Euleriano (também chamado de ciclo Euleriano ou passeio de Euler) é uma caminhada fechada que usa cada borda exatamente uma vez. Um gráfico Euleriano é um gráfico que possui um circuito Euleriano. Para um gráfico não direcionado, isso significa que o gráfico está conectado e cada vértice tem um grau par. Para um gráfico direcionado, isso significa que o gráfico está fortemente conectado e cada vértice tem grau de entrada igual ao grau de saída. Em alguns casos, o requisito de conectividade é afrouxado e um gráfico que atende apenas aos requisitos de grau é chamado de Euleriano.
até: Divisível por dois; por exemplo, um ciclo par é um ciclo cuja duração é par.
expansor: Um gráfico expansor é um gráfico cuja expansão de borda, expansão de vértice ou expansão espectral é limitada a zero.
expansão: 1. A expansão borda, número isoperimétrica, ou constante de Cheeger de um gráfico $G$ é o rácio mínimo, sobre subconjuntos $S$ de, no máximo, metade dos vértices $L$ , do número de arestas que saem $S$ para o número de vértices em $S$ .; 2. A expansão do vértice, número isoperimétrico do vértice ou ampliação de um gráfico $G$ é a razão mínima, sobre subconjuntos $S$ de no máximo metade dos vértices de $G$ , do número de vértices externos, mas adjacentes a $S,$ ao número de vértices em $S$ .; 3. A expansão vizinho única de um gráfico $G$ é o rácio mínimo, sobre subconjuntos de, no máximo, metade dos vértices de $L$ , do número de vértices exteriores $S$ , mas adjacente a um único vértice em $S$ para o número de vértices em $S$ .; 4. A expansão espectral de um grafo $d-$ regular $G$ é a lacuna espectral entre o maior autovalor $d$ de sua matriz de adjacência e o segundo maior autovalor.; 5. Uma família de gráficos tem expansão limitada se todos os seus $r-$ menores menores têm uma proporção de arestas para vértices limitada por uma função de $r$ , e expansão polinomial se a função de $r$ é um polinômio.

F

enfrentar: Em um gráfico plano ou incorporação de gráfico , um componente conectado do subconjunto do plano ou superfície da incorporação que é separado do gráfico. Para uma incorporação no plano, todas as faces, exceto uma, serão limitadas; a única face excepcional que se estende até o infinito é chamada de face externa.
fator: Um fator de um gráfico é um subgráfico de abrangência: um subgráfico que inclui todos os vértices do gráfico. O termo é usado principalmente no contexto de subgráficos regulares: um fator $k$ é um fator que é $k-$ regular. Em particular, um fator $1$ é a mesma coisa que uma combinação perfeita. Um gráfico de fator crítico é um gráfico para o qual a exclusão de qualquer vértice produz um gráfico com um fator $1$ .
fatoração: Uma fatoração de gráfico é uma partição das arestas do gráfico em fatores; uma $k$ -factorização é uma partição em $k$ -factors. Por exemplo, uma fatoração- $1$ é uma coloração de arestas com a propriedade adicional de que cada vértice incide em uma aresta de cada cor.
família: Sinônimo de classe .
finito: Um gráfico é finito se tiver um número finito de vértices e um número finito de arestas. Muitas fontes assumem que todos os gráficos são finitos sem dizer isso explicitamente. Um grafo é localmente finito se cada vértice tem um número finito de arestas incidentes. Um grafo infinito é um grafo que não é finito: tem infinitos vértices, infinitos arestas ou ambos.
primeira ordem: A lógica de primeira ordem dos gráficos é uma forma de lógica na qual as variáveis representam os vértices de um gráfico, e existe um predicado binário para testar se dois vértices são adjacentes. Para ser diferenciado da lógica de segunda ordem, na qual as variáveis também podem representar conjuntos de vértices ou arestas.
-flap: Para um conjunto de vértices $X$ , um $X$ -flap é um componente ligado do subgráfico induzida formado por exclusão $X$ . A terminologia de flap é comumente usada no contexto de paraísos , funções que mapeiam pequenos conjuntos de vértices para seus flaps. Veja também a ponte de um ciclo, que é uma aba dos vértices do ciclo ou uma corda do ciclo.
proibido: Uma caracterização proibida de grafos é a caracterização de uma família de grafos como sendo os grafos que não possuem certos outros grafos como subgráficos, subgráficos induzidos ou menores. Se $H$ for um dos gráficos que não ocorre como subgrafo, subgrafo induzido ou menor, então $H$ é considerado proibido.
floresta: Uma floresta é um grafo não direcionado sem ciclos (uma união disjunta de árvores não enraizadas) ou um grafo direcionado formado como uma união disjunta de árvores enraizadas.
Frucht: 1. Robert Frucht; 2. O gráfico de Frucht , um dos dois menores gráficos cúbicos sem simetrias não triviais.; 3. Teorema de Frucht de que todo grupo finito é o grupo de simetrias de um grafo finito.
cheio: Sinônimo de induzido .
gráfico funcional: Um gráfico funcional é um gráfico direcionado onde cada vértice tem um grau de saída. Equivalentemente, um gráfico funcional é uma pseudofloresta dirigida máxima.

G

G: Uma variável freqüentemente usada para denotar um gráfico.
gênero: O gênero de um gráfico é o gênero mínimo de uma superfície na qual ele pode ser embutido; veja incorporação .
geodésico: Como substantivo, geodésico é sinônimo de caminho mais curto . Quando usado como um adjetivo, significa relacionado aos caminhos mais curtos ou distâncias dos caminhos mais curtos.
gigante: Na teoria dos gráficos aleatórios , um componente gigante é um componente conectado que contém uma fração constante dos vértices do gráfico. Em modelos padrão de gráficos aleatórios, normalmente há no máximo um componente gigante.
circunferência: A circunferência de um gráfico é o comprimento de seu ciclo mais curto.
gráfico: O objeto fundamental de estudo na teoria dos grafos, um sistema de vértices conectados em pares por arestas. Freqüentemente subdividido em gráficos direcionados ou gráficos não direcionados, de acordo com a orientação ou não das arestas. Os gráficos mistos incluem os dois tipos de arestas.
ambicioso: Produzido por um algoritmo ganancioso . Por exemplo, uma coloração gananciosa de um gráfico é uma coloração produzida considerando os vértices em alguma sequência e atribuindo a cada vértice a primeira cor disponível.
Grötzsch: 1. Herbert Grötzsch; 2. O gráfico de Grötzsch , o menor gráfico sem triângulo que requer quatro cores em qualquer coloração adequada.; 3. Teorema de Grötzsch de que os gráficos planares sem triângulos podem sempre ser coloridos com no máximo três cores.
Número Grundy: 1. O número de Grundy de um gráfico é o número máximo de cores produzidas por uma coloração gananciosa , com uma ordem de vértice mal escolhida.

H

H: Uma variável muitas vezes utilizado para designar um gráfico, especialmente quando um outro gráfico já foi indicado por $L$ .
H- coloração: Uma $H$ -coloring de um gráfico $G$ (onde $H$ é também um gráfico) é um homomorphism de $H$ para $L$ .
H- free: Um gráfico é livre de $H$ se não tiver um subgráfico induzido isomórfico a $H$ , ou seja, se $H$ for um subgráfico induzido proibido. Os gráficos sem $H$ são a família de todos os gráficos (ou, freqüentemente, todos os gráficos finitos) que são sem $H.$ Por exemplo, os gráficos sem triângulo são os gráficos que não têm um gráfico de triângulo como subgráfico. A propriedade de ser livre de $H$ é sempre hereditária. Um gráfico é $H$ -minor-livre, se ele não tem um isomorfo menor para $H$ .
Hadwiger: 1. Hugo Hadwiger; 2. O número de Hadwiger de um gráfico é a ordem do maior menor completo do gráfico. É também chamado de número de clique de contração ou grau de homomorfismo.; 3. A conjectura de Hadwiger é a conjectura de que o número de Hadwiger nunca é menor que o número cromático.
Hamiltoniano: Um caminho hamiltoniano ou ciclo hamiltoniano é um caminho de abrangência simples ou ciclo de abrangência simples: ele cobre todos os vértices no gráfico exatamente uma vez. Um gráfico é hamiltoniano se contiver um ciclo hamiltoniano e rastreável se contiver um caminho hamiltoniano.
refúgio: Um $k$ - porto é uma função que mapeia cada conjunto $X$ com menos de $k$ vértices para um de seus flaps, geralmente satisfazendo condições adicionais de consistência. A ordem de um refúgio é o número $k$ . Os portos podem ser usados para caracterizar a largura da árvore de gráficos finitos e as extremidades e números de Hadwiger de gráficos infinitos.
altura: 1. A altura de um nó em uma árvore enraizada é o número de arestas em um caminho máximo, indo para longe da raiz (ou seja, seus nós têm profundidade estritamente crescente), que começa naquele nó e termina em uma folha.; 2. A altura de uma árvore enraizada é a altura de sua raiz. Ou seja, a altura de uma árvore é o número de arestas em um caminho mais longo possível, indo para longe da raiz, que começa na raiz e termina em uma folha.; 3. A altura de um gráfico acíclico direcionado é o comprimento máximo de um caminho direcionado neste gráfico.
hereditário: Uma propriedade hereditária de gráficos é uma propriedade que é fechada sob subgráficos induzidas: se $L$ tem uma propriedade hereditária, em seguida, por isso deve cada induzida subgráfico de $L$ . Compare monótono (fechado em todos os subgráficos) ou menor-fechado (fechado em menores).
hexágono: Um ciclo simples que consiste em exatamente seis arestas e seis vértices.
buraco: Um buraco é um ciclo induzido de quatro ou mais comprimento. Um buraco estranho é um buraco de comprimento estranho. Um anti-furo é um subgrafo induzido de ordem quatro cujo complemento é um ciclo; equivalentemente, é uma lacuna no gráfico do complemento. Esta terminologia é usada principalmente no contexto de gráficos perfeitos, que são caracterizados pelo teorema do gráfico perfeito forte como sendo os gráficos sem orifícios ímpares ou antifuros ímpares. Os gráficos sem buracos são iguais aos gráficos de acordes .
equivalência homomórfica: Dois gráficos são homomorficamente equivalentes se houver dois homomorfismos, um de cada gráfico para o outro gráfico.
homomorfismo: 1. Um homomorfismo de grafo é um mapeamento do conjunto de vértices de um grafo para o conjunto de vértices de outro grafo que mapeia vértices adjacentes para vértices adjacentes. Este tipo de mapeamento entre grafos é o mais comumente usado em abordagens da teoria de categorias para a teoria dos grafos. Uma coloração de gráfico adequada pode ser descrita equivalentemente como um homomorfismo para um gráfico completo.; 2. O grau de homomorfismo de um grafo é sinônimo de seu número de Hadwiger , a ordem do maior clique menor.
hyperedge: Uma aresta em um hipergrafo , tendo qualquer número de extremidades, em contraste com o requisito de que as arestas dos gráficos tenham exatamente duas extremidades.
hipercubo: Um gráfico de hipercubo é um gráfico formado a partir dos vértices e arestas de um hipercubo geométrico .
hipergrafo: Um hipergrafo é uma generalização de um gráfico em que cada aresta (chamada de hipercarga neste contexto) pode ter mais de dois pontos finais.
hipopótamo-: Este prefixo, em combinação com uma propriedade de gráfico, indica um gráfico que não possui a propriedade, mas de tal forma que todo subgráfico formado pela exclusão de um único vértice possui a propriedade. Por exemplo, um gráfico hipohamiltoniano é aquele que não tem um ciclo hamiltoniano, mas para o qual cada deleção de um vértice produz um subgrafo hamiltoniano. Compare crítico , usado para gráficos que têm uma propriedade, mas para os quais cada deleção de um vértice não tem.

eu

em grau: O número de arestas de entrada em um gráfico direcionado; veja grau .
incidência: Uma incidência em um gráfico é um par de arestas de vértices de forma que o vértice seja um ponto final da aresta.
matriz de incidência: A matriz de incidência de um gráfico é uma matriz cujas linhas são indexadas por vértices do gráfico, e cujas colunas são indexadas por arestas, com um na célula para a linha $i$ e coluna $j$ quando o vértice $i$ e a aresta $j$ são incidentes, e um zero caso contrário.
incidente: A relação entre uma aresta e um de seus pontos finais.
incomparabilidade: Um gráfico de incomparabilidade é o complemento de um gráfico de comparabilidade ; veja a comparabilidade .
independente: 1. Um conjunto independente é um conjunto de vértices que induz um subgrafo sem bordas. Também pode ser chamado de conjunto estável ou coclique. O número de independência $α (G)$ é o tamanho do conjunto independente máximo .; 2. No matroide gráfico de um gráfico, um subconjunto de arestas é independente se o subgráfico correspondente for uma árvore ou floresta. Na matróide bicircular , um subconjunto de arestas é independente se o subgrafo correspondente for uma pseudofloresta .
indiferença: Um gráfico de indiferença é outro nome para um gráfico de intervalo adequado ou gráfico de intervalo de unidade; veja bem .
induzido: Um subgráfico induzido ou subgráfico completo de um gráfico é um subgráfico formado a partir de um subconjunto de vértices e de todas as arestas que possuem ambos os pontos finais no subconjunto. Casos especiais incluem caminhos e ciclos induzidos, subgráficos induzidos que são caminhos ou ciclos.
indutivo: Sinônimo de degenerado .
infinito: Um gráfico infinito é aquele que não é finito; veja finito .
interno: Um vértice de um caminho ou árvore é interno se não for uma folha; isto é, se seu grau for maior que um. Dois caminhos são internamente disjuntos (algumas pessoas chamam de independentes ) se não tiverem nenhum vértice em comum, exceto o primeiro e o último.
interseção: 1. A interseção de dois gráficos é seu maior subgrafo comum, o gráfico formado pelos vértices e arestas que pertencem a ambos os gráficos.; 2. Um gráfico de interseção é um gráfico cujos vértices correspondem a conjuntos ou objetos geométricos, com uma aresta entre dois vértices exatamente quando os dois conjuntos ou objetos correspondentes têm uma interseção não vazia. Várias classes de gráficos podem ser definidas como os gráficos de interseção de certos tipos de objetos, por exemplo, gráficos de cordas (gráficos de interseção de subárvores de uma árvore), gráficos de círculo (gráficos de interseção de cordas de um círculo), gráficos de intervalo (gráficos de interseção de intervalos de uma linha), grafos de linha (grafos de interseção das arestas de um grafo) e grafos de clique (grafos de interseção dos cliques máximos de um grafo). Cada gráfico é um gráfico de interseção para alguma família de conjuntos, e essa família é chamada de representação de interseção do gráfico. O número de intersecção de um gráfico $G$ é o número total mínimo de elementos em qualquer representação intersecção de $L$ .
intervalo: 1. Um gráfico de intervalo é um gráfico de interseção de intervalos de uma linha .; 2. O intervalo $[u, v]$ em um gráfico é a união de todos os caminhos mais curtos de $u$ a $v$ .; 3. A espessura do intervalo é sinônimo de largura do caminho .
invariante: Sinônimo de propriedade .
flecha invertida: Uma flecha com direção oposta em comparação com outra flecha. A seta $(y, x)$ é a seta invertida da seta $(x, y)$ .
isolado: Um vértice isolado de um grafo é um vértice cujo grau é zero, ou seja, um vértice sem arestas incidentes.
isomórfico: Dois gráficos são isomórficos se houver um isomorfismo entre eles; veja isomorfismo .
isomorfismo: Um isomorfismo de gráfico é uma incidência um-para-um que preserva a correspondência dos vértices e arestas de um gráfico com os vértices e arestas de outro gráfico. Dois gráficos relacionados dessa forma são considerados isomórficos.
isoperimétrico: Veja expansão .
istmo: Sinônimo de ponte , no sentido de uma aresta cuja remoção desconecta o gráfico.

K

K: Para a notação para gráficos completos, gráficos bipartidos completos e gráficos multipartidos completos, consulte o completo .
κ: $κ (G)$ (usando a letra grega kappa) é a ordem da clique máxima em $G$ ; veja clique .
núcleo: Um kernel de um gráfico direcionado é um conjunto de vértices que é estável e absorvente .
nó: Uma seção inevitável de um gráfico direcionado . Veja nó (matemática) e teoria do nó .

eu

eu: $L (G)$ é o gráfico linear de $G$ ; veja a linha .
rótulo: 1. Informações associadas a um vértice ou borda de um gráfico. Um gráfico rotulado é um gráfico cujos vértices ou arestas possuem rótulos. Os termos rotulado por vértice ou rotulado por aresta podem ser usados para especificar quais objetos de um gráfico têm rótulos. A rotulagem de gráfico refere-se a vários problemas diferentes de atribuição de rótulos a gráficos sujeitos a certas restrições. Consulte também a coloração do gráfico , em que os rótulos são interpretados como cores.; 2. No contexto de enumeração de gráfico , os vértices de um gráfico são chamados de rotulados se forem todos distinguíveis uns dos outros. Por exemplo, isso pode ser feito fixando-se uma correspondência um-para-um entre os vértices e os inteiros de 1 para a ordem do gráfico. Quando os vértices são rotulados, os gráficos que são isomórficos entre si (mas com ordenações de vértices diferentes) são contados como objetos separados. Em contraste, quando os vértices não estão rotulados, os gráficos isomórficos entre si não são contados separadamente.
Folha: 1. Um vértice de folha ou vértice pendente (especialmente em uma árvore) é um vértice cujo grau é $1$ . Uma aresta de folha ou aresta pendente é a aresta que conecta um vértice de folha a seu único vizinho.; 2. Um poder de folha de uma árvore é um gráfico cujos vértices são as folhas da árvore e cujas bordas conectam folhas cuja distância na árvore é no máximo um determinado limite.
comprimento: Em um gráfico não ponderado, o comprimento de um ciclo, caminho ou caminhada é o número de arestas que ele usa. Em um gráfico ponderado, pode ser a soma dos pesos das arestas que usa. O comprimento é usado para definir o caminho mais curto , a circunferência (comprimento do ciclo mais curto) e o caminho mais longo entre dois vértices em um gráfico.
nível: 1. Esta é a profundidade de um nó mais 1, embora alguns a definam como sinônimo de profundidade . O nível de um nó em uma árvore com raiz é o número de nós no caminho da raiz ao nó. Por exemplo, a raiz tem nível 1 e qualquer um de seus nós adjacentes tem nível 2.; 2. Um conjunto de todos os nós com o mesmo nível ou profundidade.
linha: Um sinônimo para uma aresta não direcionada. O gráfico de linha $G (G)$ de um gráfico $G$ é um gráfico com um vértice de cada ponta de $L$ e uma borda para cada par de bordas que partilham um ponto de extremidade em $L$ .
ligação: Sinônimo de degenerescência .
Lista: 1. Uma lista de adjacências é uma representação computacional de grafos para uso em algoritmos de grafos.; 2. A coloração da lista é uma variação da coloração do gráfico em que cada vértice possui uma lista de cores disponíveis.
local: Uma propriedade local de um gráfico é determinada apenas pela vizinhança dos vértices no gráfico. Por exemplo, um gráfico é localmente finito se todas as suas vizinhanças são finitas.
ciclo: Um loop ou self-loop é uma aresta cujos pontos finais são o mesmo vértice. Ele forma um ciclo de duração $1$ . Isso não é permitido em gráficos simples.

M

ampliação: Sinônimo de expansão de vértice .
Coincidindo: Uma correspondência é um conjunto de arestas nas quais não há dois vértices. Um vértice é correspondido ou saturado se for um dos pontos finais de uma aresta na correspondência. Uma combinação perfeita ou combinação completa é aquela que corresponde a cada vértice; ele também pode ser chamado de fator 1 e só pode existir quando a ordem é par. Uma correspondência quase perfeita, em um gráfico com ordem ímpar, é aquela que satura todos, exceto um vértice. Uma correspondência máxima é aquela que usa tantas arestas quanto possível; o número correspondente $α' (G)$ de um gráfico $G$ é o número de arestas em um casamento máximo. Uma correspondência máxima é aquela à qual nenhuma aresta adicional pode ser adicionada.
maximal: 1. Um subgrafo de dado grafo $G$ é maximal para uma propriedade particular se tiver essa propriedade, mas nenhum outro supergrafo dele que também seja um subgrafo de $G$ também tem a mesma propriedade. Ou seja, é um elemento máximo dos subgráficos com a propriedade. Por exemplo, um clique máximo é um subgráfico completo que não pode ser expandido para um subgráfico completo maior. A palavra "máximo" deve ser distinguida de "máximo": um subgráfico máximo é sempre máximo, mas não necessariamente vice-versa.; 2. Um gráfico simples com uma determinada propriedade é máximo para aquela propriedade se não for possível adicionar mais arestas a ele (mantendo o conjunto de vértices inalterado) enquanto preserva a simplicidade do gráfico e a propriedade. Assim, por exemplo, um grafo planar máximo é um grafo planar tal que adicionar mais arestas a ele criaria um grafo não plano.
máximo: Um subgráfico de um dado gráfico $G$ é máximo para uma propriedade particular se for o maior subgráfico (por ordem ou tamanho) entre todos os subgráficos com aquela propriedade. Por exemplo, um clique máximo é qualquer um dos maiores cliques em um dado grafo.
mediana: 1. Uma mediana de um triplo de vértices, um vértice que pertence aos caminhos mais curtos entre todos os pares de vértices, especialmente em gráficos de mediana e gráficos modulares .; 2. Um gráfico de mediana é um gráfico em que cada três vértices tem uma mediana única.
Meyniel: 1. Henri Meyniel, teórico francês dos grafos.; 2. Um gráfico de Meyniel é um gráfico em que cada ciclo ímpar de cinco ou mais cordas tem pelo menos dois acordes.
mínimo: Um subgráfico de determinado gráfico é mínimo para uma propriedade particular se tiver essa propriedade, mas nenhum subgráfico adequado também tem a mesma propriedade. Ou seja, é um elemento mínimo dos subgráficos com a propriedade.
corte mínimo: Um corte cujo conjunto de corte tem peso total mínimo, possivelmente restrito a cortes que separam um determinado par de vértices; eles são caracterizados pelo teorema de corte mínimo de fluxo máximo .
menor: Um gráfico $H$ é um menor de um outro gráfico $G$ se $H$ pode ser obtido por exclusão arestas ou vértices de $L$ e contrair bordas em $L$ . É um menor raso se puder ser formado como um menor de tal forma que os subgráficos de $G$ que foram contraídos para formar os vértices de $H$ tenham todos pequenos diâmetros. $H$ é um menor topológica de $L$ se $L$ tem um subgráfico que é uma subdivisão de $H$ . Um gráfico é livre de $H$ menor se não tiver $H$ como menor. Uma família de gráficos é fechada para menores se for fechada para menores; o teorema de Robertson-Seymour caracteriza as famílias menores fechadas como tendo um conjunto finito de menores proibidos .
misturado: Um gráfico misto é um gráfico que pode incluir arestas direcionadas e não direcionadas.
modular: 1. Grafo modular , um grafo no qual cada tripla de vértices tem pelo menos um vértice mediano que pertence aos caminhos mais curtos entre todos os pares da tripla.; 2. Decomposição modular , uma decomposição de um gráfico em subgráficos dentro dos quais todos os vértices se conectam ao resto do gráfico da mesma maneira.; 3. Modularidade de um agrupamento de grafo, a diferença entre o número de arestas do cluster cruzado e seu valor esperado.
monótono: Uma propriedade monótona dos gráficos é uma propriedade que é fechada sob os subgráficos: se $G$ tem uma propriedade hereditária, então todos os subgráficos de $G$ também devem . Compare hereditário (fechado em subgráficos induzidos) ou menor-fechado (fechado em menores).
Gráfico de Moore: Um gráfico de Moore é um gráfico regular para o qual o limite de Moore é atingido com exatidão. O limite de Moore é uma desigualdade que relaciona o grau, o diâmetro e a ordem de um gráfico, provada por Edward F. Moore . Cada gráfico de Moore é uma gaiola.
multigrafo: Um multigrafo é um grafo que permite múltiplas adjacências (e, freqüentemente, auto-loops); um gráfico que não precisa ser simples.
adjacência múltipla: Uma adjacência múltipla ou aresta múltipla é um conjunto de mais de uma aresta, todas com os mesmos pontos finais (na mesma direção, no caso de grafos direcionados). Um gráfico com arestas múltiplas é freqüentemente denominado multigrafo.
multiplicidade: A multiplicidade de uma aresta é o número de arestas em uma adjacência múltipla. A multiplicidade de um gráfico é a multiplicidade máxima de qualquer uma de suas arestas.

N

N: 1. Para a notação para vizinhanças abertas e fechadas, consulte vizinhança .; 2. Um $n$ minúsculo é freqüentemente usado (especialmente em ciência da computação) para denotar o número de vértices em um dado gráfico.
vizinho
vizinho: Um vértice adjacente a um determinado vértice.
vizinhança
vizinhança: A vizinhança aberta (ou vizinhança) de um vértice $v$ é o subgrafo induzido por todos os vértices adjacentes a $v$ . A vizinhança fechada é definida da mesma maneira, mas também inclui o próprio $v$ . A vizinhança aberta de $v$ em $G$ pode ser denotada como $N G (v)$ ou $N (v)$ , e a vizinhança fechada pode ser denotada como $N G [v]$ ou $N [v]$ . Quando a abertura ou fechamento de uma vizinhança não é especificada, presume-se que ela seja aberta.
rede: Um gráfico no qual atributos (por exemplo, nomes) estão associados aos nós e / ou arestas.
nó: Um sinônimo para vértice .
sem borda: Um non-edge ou anti-edge é um par de vértices que não são adjacentes; as arestas do gráfico do complemento.
gráfico nulo: Veja o gráfico vazio .

O

ímpar: 1. Um ciclo ímpar é um ciclo cuja duração é ímpar. A circunferência ímpar de um gráfico não bipartido é o comprimento de seu ciclo ímpar mais curto. Um buraco ímpar é um caso especial de um ciclo ímpar: aquele que é induzido e tem quatro ou mais vértices.; 2. Um vértice ímpar é um vértice cujo grau é ímpar. Pelo lema do handshaking, todo grafo finito não direcionado tem um número par de vértices ímpares.; 3. Uma orelha ímpar é um caminho ou ciclo simples com um número ímpar de arestas, usado em decomposições de orelhas ímpares de gráficos de fator crítico; ver ouvido .; 4. Um acorde ímpar é uma aresta que conecta dois vértices que estão a uma distância ímpar em um ciclo par. Acordes ímpares são usados para definir gráficos de acordes fortes .; 5. Um gráfico ímpar é um caso especial de um gráfico de Kneser , tendo um vértice para cada $(n - 1)$ subconjunto de elemento de um $(2 n - 1)$ conjunto de elemento, e uma aresta conectando dois subconjuntos quando seus conjuntos correspondentes são disjuntar.
abrir: 1. Veja a vizinhança .; 2. Veja andar .
pedido: 1. A ordem de um grafo $G$ é o número de seus vértices, $| V (G) |$ . A variável $n$ é freqüentemente usada para esta quantidade. Veja também o tamanho , o número de arestas.; 2. Um tipo de lógica de gráficos ; veja primeira ordem e segunda ordem .; 3. Uma ordem ou ordenação de um gráfico é um arranjo de seus vértices em uma sequência, especialmente no contexto de ordenação topológica (uma ordem de um gráfico acíclico dirigido em que cada aresta vai de um vértice anterior para um vértice posterior na ordem ) e ordenação de degenerescência (uma ordem na qual cada vértice tem grau mínimo no subgrafo induzido dele e todos os vértices posteriores).; 4. Para a ordem de um refúgio ou amoreira-brava, consulte refúgio e amora silvestre .
orientação
orientado: 1. A orientação de um gráfico não direcionado é uma atribuição de direções às suas arestas, transformando-o em um gráfico direcionado. Um gráfico orientado é aquele que recebeu uma orientação. Assim, por exemplo, uma polytree é uma árvore orientada; difere de uma árvore direcionada (uma arborescência) por não haver exigência de consistência nas direções de suas bordas. Outros tipos especiais de orientação incluem torneios , orientações de gráficos completos; orientações fortes , orientações fortemente conectadas; orientações acíclicas , orientações acíclicas; Orientações eulerianas , orientações que são eulerianas; e orientações transitivas , orientações que são transitivamente fechadas.; 2. Grafo orientado, utilizado por alguns autores como sinónimo de grafo dirigido .
grau superior: Veja o grau .
exterior: Veja o rosto .
planar externo: Um grafo planar externo é um grafo que pode ser embutido no plano (sem cruzamentos) de forma que todos os vértices fiquem na face externa do grafo.

P

caminho: Um caminho pode ser uma caminhada ou uma caminhada sem vértices repetidos e, conseqüentemente, bordas (também chamado de caminho simples), dependendo da origem. Casos especiais importantes incluem caminhos induzidos e caminhos mais curtos .
decomposição de caminho: Uma decomposição de caminho de um grafo $G$ é uma decomposição em árvore cuja árvore subjacente é um caminho. Sua largura é definida da mesma forma que para as decomposições de árvores, como um a menos que o tamanho do saco maior. A largura mínima de uma decomposição caminho de $L$ é a largura de caminho de $L$ .
largura do caminho: A largura de caminho de um gráfico que $L$ é a largura mínima de um percurso de decomposição $L$ . Ele também pode ser definida em termos do número de clique de um intervalo de conclusão $L$ . É sempre entre a largura de banda ea treewidth de $G$ . Também é conhecido como espessura de intervalo, número de separação de vértice ou número de pesquisa de nó.
pingente: Veja a folha .
perfeito: 1. Um gráfico perfeito é um gráfico no qual, em cada subgrafo induzido, o número cromático é igual ao número do clique. O teorema do gráfico perfeito e o teorema do gráfico perfeito forte são dois teoremas sobre gráficos perfeitos, o primeiro provando que seus complementos também são perfeitos e o último provando que eles são exatamente os gráficos sem orifícios estranhos ou anti-orifícios.; 2. Um gráfico perfeitamente ordenável é um gráfico cujos vértices podem ser ordenados de tal forma que um algoritmo de coloração ganancioso com esta ordenação colore de forma otimizada todos os subgráficos induzidos. Os gráficos perfeitamente organizáveis são uma subclasse dos gráficos perfeitos.; 3. Uma combinação perfeita é aquela que satura todos os vértices; veja correspondência .; 4. Uma 1-fatoração perfeita é uma partição das arestas de um gráfico em correspondências perfeitas, de modo que cada duas correspondências formem um ciclo hamiltoniano.
periférico: 1. Um ciclo periférico ou ciclo sem separação é um ciclo com no máximo uma ponte.; 2. Um vértice periférico é um vértice cuja excentricidade é máxima. Em uma árvore, isso deve ser uma folha.
Petersen: 1. Julius Petersen (1839–1910), teórico de grafos dinamarquês.; 2. O gráfico de Petersen , um gráfico de 10 vértices e 15 arestas freqüentemente usado como contra-exemplo.; 3. Teorema de Petersen de que todo grafo cúbico sem ponte tem uma combinação perfeita.
planar: Um grafo planar é um grafo que se embebe no plano euclidiano. Um gráfico plano é um gráfico plano para o qual uma incorporação específica já foi corrigida. Um gráfico $k$ -planar é aquele que pode ser desenhado no plano com no máximo $k$ cruzamentos por aresta.
polytree: Uma polytree é uma árvore orientada; equivalentemente, um grafo acíclico dirigido cujo grafo não dirigido subjacente é uma árvore.
potência: 1. Um gráfico de potência $G k$ de um gráfico $G$ é outro gráfico no mesmo conjunto de vértices; dois vértices são adjacentes em $L k$ quando estão a uma distância de, no máximo, $k$ em $L$ . O poder da folha é um conceito intimamente relacionado, derivado do poder de uma árvore tomando o subgrafo induzido pelas folhas da árvore.; 2. A análise de Power Graph é um método para analisar redes complexas, identificando cliques, bicliques e estrelas dentro da rede.; 3. As leis de potência nas distribuições de graus de redes sem escala são um fenômeno em que o número de vértices de um determinado grau é proporcional a uma potência do grau.
antecessor: Um vértice que vem antes de um determinado vértice em um caminho direcionado .
apropriado: 1. Um subgrafo adequado é um subgrafo que remove pelo menos um vértice ou aresta em relação a todo o gráfico; para gráficos finitos, os subgráficos apropriados nunca são isomórficos ao gráfico inteiro, mas para gráficos infinitos eles podem ser.; 2. Uma coloração apropriada é uma atribuição de cores aos vértices de um gráfico (uma coloração) que atribui cores diferentes aos pontos finais de cada aresta; veja a cor .; 3. Um gráfico de intervalo adequado ou gráfico de arco circular adequado é um gráfico de interseção de uma coleção de intervalos ou arcos circulares (respectivamente) de modo que nenhum intervalo ou arco contenha outro intervalo ou arco. Os gráficos de intervalo adequados também são chamados de gráficos de intervalo de unidade (porque podem sempre ser representados por intervalos de unidade) ou gráficos de indiferença.
propriedade: Uma propriedade de gráfico é algo que pode ser verdadeiro para alguns gráficos e falso para outros, e que depende apenas da estrutura do gráfico e não de informações incidentais, como rótulos. As propriedades do gráfico podem ser descritas de forma equivalente em termos de classes de gráficos (os gráficos que possuem uma determinada propriedade). Mais geralmente, uma propriedade de gráfico também pode ser uma função de gráficos que, novamente, é independente de informações incidentais, como o tamanho, a ordem ou a sequência de graus de um gráfico; esta definição mais geral de uma propriedade também é chamada de invariante do gráfico.
pseudofloresta: Uma pseudofloresta é um grafo não direcionado no qual cada componente conectado tem no máximo um ciclo, ou um grafo direcionado no qual cada vértice tem no máximo uma aresta de saída.
pseudógrafo: Um pseudógrafo é um gráfico ou multigrafo que permite auto-loops.

Q

gráfico de quase linha: Um grafo quase linear ou grafo localmente co-bipartido é um grafo no qual a vizinhança aberta de cada vértice pode ser particionada em dois cliques. Esses gráficos são sempre livres de garras e incluem como um caso especial os gráficos de linha . Eles são usados na teoria da estrutura de grafos sem garras.
tremor: Uma aljava é um multigrafo direcionado, conforme usado na teoria das categorias . As pontas de uma aljava são chamadas de flechas.

R

raio: O raio de um gráfico é a excentricidade mínima de qualquer vértice.
Ramanujan: Um gráfico Ramanujan é um gráfico cuja expansão espectral é a maior possível. Ou seja, é um grafo $d-$ regular, de modo que o segundo maior autovalor de sua matriz de adjacência é no máximo . ${\ displaystyle 2 {\ sqrt {d-1}}}$
raio: Um raio, em um gráfico infinito, é um caminho simples infinito com exatamente um ponto final. As extremidades de um gráfico são classes de equivalência de raios.
acessibilidade: A capacidade de ir de um vértice a outro em um gráfico .
alcançável: Tem uma acessibilidade afirmativa . Diz-se que um vértice $y$ pode ser alcançado a partir de um vértice $x$ se existir um caminho de $x$ para $y$ .
reconhecível: No contexto da conjectura de reconstrução , uma propriedade de gráfico é reconhecível se sua verdade puder ser determinada a partir do deck do gráfico. Muitas propriedades de gráfico são reconhecidas como reconhecíveis. Se a conjectura de reconstrução for verdadeira, todas as propriedades do gráfico são reconhecíveis.
reconstrução: A conjectura de reconstrução afirma que cada grafo não direcionado $G$ é determinado exclusivamente por seu baralho , um multiconjunto de grafos formado pela remoção de um vértice de $G$ de todas as maneiras possíveis. Nesse contexto, reconstrução é a formação de um grafo a partir de seu deck.
retângulo: Um ciclo simples que consiste em exatamente quatro arestas e quatro vértices.
regular: Um gráfico é $d-$ regular quando todos os seus vértices têm grau $d$ . Um gráfico regular é um gráfico que é $d-$ regular para alguns $d$ .
torneio regular: Um torneio regular é um torneio em que in-degree é igual a out-degree para todos os vértices.
reverter: Veja transpor .
raiz: 1. Um vértice designado em um gráfico, particularmente em árvores direcionadas e gráficos enraizados .; 2. A operação inversa para a potência de um gráfico : uma $k-$ ésima raiz de um gráfico $G$ é outro gráfico no mesmo conjunto de vértices de modo que dois vértices são adjacentes em $G$ se e somente se eles têm distância no máximo $k$ na raiz.

S

segunda ordem: A lógica de segunda ordem dos gráficos é uma forma de lógica na qual as variáveis podem representar vértices, arestas, conjuntos de vértices e (às vezes) conjuntos de arestas. Essa lógica inclui predicados para testar se um vértice e uma aresta são incidentes, bem como se um vértice ou aresta pertence a um conjunto. Para ser distinguido da lógica de primeira ordem, na qual as variáveis só podem representar vértices.
saturado: Veja correspondência .
procurando numero: O número de pesquisa do nó é sinônimo de largura do caminho .
auto-loop: Sinônimo de loop .
vértice de separação: Veja o ponto de articulação .
número de separação: O número de separação do vértice é sinônimo de largura do caminho .
simples: 1. Um grafo simples é um grafo sem loops e sem múltiplas adjacências. Ou seja, cada aresta conecta dois pontos finais distintos e não há duas arestas com os mesmos pontos finais. Uma aresta simples é uma aresta que não faz parte de uma adjacência múltipla. Em muitos casos, os gráficos são considerados simples, a menos que especificado de outra forma.; 2. Um caminho simples ou um ciclo simples é um caminho ou ciclo que não tem vértices repetidos e, conseqüentemente, não tem arestas repetidas.
Pia: Um sumidouro, em um gráfico direcionado, é um vértice sem arestas de saída (grau de saída igual a 0).
Tamanho: O tamanho de um grafo $G$ é o número de suas arestas, $| E (G) |$ . A variável $m$ é freqüentemente usada para esta quantidade. Veja também ordem , o número de vértices.
rede de pequeno mundo: Uma rede de mundo pequeno é um gráfico no qual a maioria dos nós não são vizinhos uns dos outros, mas a maioria dos nós pode ser alcançada de todos os outros nós por um pequeno número de saltos ou etapas. Especificamente, uma rede de pequeno mundo é definida como um gráfico onde a distância típica L entre dois nós escolhidos aleatoriamente (o número de etapas necessárias) cresce proporcionalmente ao logaritmo do número de nós N na rede
snark: Um snark é um gráfico cúbico simples, conectado e sem ponte com índice cromático igual a 4.
fonte: Uma fonte, em um gráfico direcionado, é um vértice sem arestas de entrada (em grau igual a 0).
espaço: Na teoria algébrica dos grafos , vários espaços vetoriais sobre o campo binário podem ser associados a um gráfico. Cada um tem conjuntos de arestas ou vértices para seus vetores e diferença simétrica de conjuntos como sua operação de soma vetorial. O espaço da aresta é o espaço de todos os conjuntos de arestas, e o espaço do vértice é o espaço de todos os conjuntos de vértices. O espaço de corte é um subespaço do espaço de borda que tem os conjuntos de corte do gráfico como seus elementos. O espaço do ciclo tem os subgráficos abrangentes eulerianos como seus elementos.
chave inglesa: Uma chave inglesa é um gráfico (geralmente esparso) cujas distâncias de caminho mais curtas se aproximam daquelas em um gráfico denso ou outro espaço métrico. As variações incluem chaves geométricas , gráficos cujos vértices são pontos em um espaço geométrico; tree spanners , árvores de abrangência de um gráfico cujas distâncias se aproximam das distâncias do gráfico, e spanners de gráfico, subgráficos esparsos de um gráfico denso cujas distâncias se aproximam das distâncias do gráfico original. Uma chave inglesa gananciosa é uma chave inglesa construída por um algoritmo ganancioso, geralmente aquele que considera todas as arestas da mais curta à mais longa e mantém aquelas que são necessárias para preservar a aproximação da distância.
abrangendo: Um subgráfico se estende quando inclui todos os vértices do gráfico fornecido. Casos importantes incluem spanning trees , spanning subgraphs que são árvores e combinações perfeitas , spanning subgraphs que são matchings. Um subgráfico de abrangência também pode ser chamado de fator , especialmente (mas não apenas) quando é regular.
escasso: Um gráfico esparso é aquele que possui poucas arestas em relação ao seu número de vértices. Em algumas definições, a mesma propriedade também deve ser verdadeira para todos os subgráficos do gráfico fornecido.
espectral
espectro: O espectro de um grafo é a coleção de autovalores de sua matriz de adjacência. A teoria dos grafos espectrais é o ramo da teoria dos grafos que usa espectros para analisar gráficos. Veja também expansão espectral .
dividir: 1. Um grafo dividido é um grafo cujos vértices podem ser particionados em um clique e um conjunto independente. Uma classe relacionada de gráficos, os gráficos de divisão dupla, são usados na prova do teorema do gráfico perfeito forte.; 2. Uma divisão de um grafo arbitrário é uma partição de seus vértices em dois subconjuntos não vazios, de forma que as arestas que abrangem esse corte formem um subgrafo bipartido completo. As divisões de um gráfico podem ser representadas por uma estrutura de árvore chamada decomposição de divisão . Uma divisão é chamada de divisão forte quando não é cruzada por nenhuma outra divisão. Uma divisão é chamada de não trivial quando ambos os lados têm mais de um vértice. Um gráfico é denominado primo quando não tem divisões não triviais.
quadrado: 1. O quadrado de um gráfico $G$ é a potência do gráfico $G 2$ ; na outra direção, $G$ é a raiz quadrada de $G 2$ . O meio-quadrado de um gráfico bipartido é o subgráfico de seu quadrado induzido por um lado da bipartição.; 2. Um quadrado é um gráfico plano que pode ser desenhado de forma que todas as faces limitadas tenham 4 ciclos e todos os vértices de grau ≤ 3 pertençam à face externa.; 3. Um gráfico de grade quadrada é um gráfico de rede definido a partir de pontos no plano com coordenadas inteiras conectadas por arestas de comprimento unitário.
estábulo: Um conjunto estável é sinônimo de um conjunto independente .
Estrela: Uma estrela é uma árvore com um vértice interno; equivalentemente, é um grafo bipartido completo $K 1, n$ para algum $n \geq 2$ . O caso especial de uma estrela com três folhas é chamado de garra.
força: A força de um gráfico é a razão mínima do número de arestas removidas do gráfico para os componentes criados, em todas as remoções possíveis; é análogo à tenacidade, com base nas remoções de vértices.
Forte: 1. Para conectividade forte e componentes fortemente conectados de gráficos direcionados, consulte conectado e componente . Uma orientação forte é uma orientação fortemente conectada; veja a orientação .; 2. Para o teorema do gráfico perfeito forte , consulte perfeito .; 3. Um grafo fortemente regular é um grafo regular no qual cada dois vértices adjacentes têm o mesmo número de vizinhos compartilhados e cada dois vértices não adjacentes têm o mesmo número de vizinhos compartilhados.; 4. Um gráfico de acordes fortes é um gráfico de acordes em que cada ciclo par de comprimento seis ou mais tem um acorde ímpar.; 5. Um grafo fortemente perfeito é um grafo no qual cada subgrafo induzido tem um conjunto independente atendendo a todos os cliques máximos. Os grafos de Meyniel também são chamados de "grafos fortemente perfeitos" porque neles cada vértice pertence a um conjunto independente.
subfloresta: Um subgrafo de uma floresta .
subgrafo: Um subgráfico de um gráfico $G$ é um outro gráfico formado a partir de um subconjunto dos vértices e arestas de $L$ . O subconjunto de vértices deve incluir todos os pontos finais do subconjunto de arestas, mas também pode incluir vértices adicionais. Um subgráfico de abrangência é aquele que inclui todos os vértices do gráfico; um subgráfico induzido é aquele que inclui todas as arestas cujos pontos finais pertencem ao subconjunto de vértices.
subárvore: Uma subárvore é um subgráfico conectado de uma árvore. Às vezes, para árvores enraizadas, as subárvores são definidas como um tipo especial de subgrafo conectado, formado por todos os vértices e arestas alcançáveis a partir de um vértice escolhido.
sucessor: Um vértice vindo após um determinado vértice em um caminho direcionado .
superconcentrador: Um superconcentrador é um gráfico com dois subconjuntos designados e de tamanhos iguais de vértices $I$ e $O$ , de modo que para cada dois subconjuntos $S$ de $I$ e $T$ $O$ de tamanhos iguais existe uma família de caminhos disjuntos conectando cada vértice em $S$ a um vértice em $T$ . Algumas fontes requerem, além disso, que um superconcentrador seja um grafo acíclico direcionado, com $I$ como suas fontes e $O$ como seus sumidouros.
supergrafo: Um gráfico formado pela adição de vértices, arestas ou ambos a um determinado gráfico. Se $H$ é um subgráfico de $G$ , então $L$ é um supergraph de $H$ .

T

theta: 1. Um grafo teta é a união de três caminhos internamente disjuntos (simples) que têm os mesmos dois vértices finais distintos.; 2. O gráfico teta de uma coleção de pontos no plano euclidiano é construído construindo um sistema de cones ao redor de cada ponto e adicionando uma aresta por cone, ao ponto cuja projeção em um raio central do cone é menor.; 3. O número de Lovász ou função teta de Lovász de um grafo é um invariante do grafo relacionado ao número do clique e ao número cromático que pode ser calculado em tempo polinomial por programação semidefinida.
topológico: 1. Um grafo topológico é uma representação dos vértices e arestas de um grafo por pontos e curvas no plano (não necessariamente evitando cruzamentos).; 2. A teoria topológica dos grafos é o estudo de embeddings de grafos.; 3. A classificação topológica é o problema algorítmico de organizar um grafo acíclico direcionado em uma ordem topológica, uma sequência de vértices de forma que cada aresta vá de um vértice anterior a um vértice posterior na sequência.
totalmente desconectado: Sinônimo de edgeless .
percorrer: Uma trilha fechada, uma caminhada que começa e termina no mesmo vértice e não tem bordas repetidas. Os passeios de Euler são passeios que usam todas as bordas do gráfico; veja Eulerian .
torneio: Um torneio é a orientação de um gráfico completo; isto é, é um gráfico direcionado tal que cada dois vértices são conectados por exatamente uma aresta direcionada (indo em apenas uma das duas direções entre os dois vértices).
rastreável: Um gráfico rastreável é um gráfico que contém um caminho hamiltoniano.
trilha: Um passeio sem bordas repetidas.
transitivo: Tem a ver com a propriedade transitiva . O fechamento transitivo de um dado grafo direcionado é um grafo no mesmo conjunto de vértices que tem uma aresta de um vértice para outro sempre que o grafo original tem um caminho conectando os mesmos dois vértices. Uma redução transitiva de um gráfico é um gráfico mínimo com o mesmo fechamento transitivo; os gráficos acíclicos direcionados têm uma redução transitiva única. Uma orientação transitiva é uma orientação de um gráfico que é seu próprio fechamento transitivo; ele existe apenas para gráficos de comparabilidade .
transpor: O gráfico de transposição de um dado gráfico direcionado é um gráfico nos mesmos vértices, com cada aresta invertida na direção. Também pode ser chamado de inverso ou reverso do gráfico.
árvore: 1. Uma árvore é um gráfico não direcionado que é conectado e acíclico, ou um gráfico direcionado no qual existe uma caminhada única de um vértice (a raiz da árvore) a todos os vértices restantes.; 2. Uma $k-$ árvore é um gráfico formado pela colagem de $(k + 1)$ -cliques em $k$ -cliques compartilhadas . Uma árvore no sentido comum é uma árvore $1 de$ acordo com esta definição.
decomposição de árvore: Uma decomposição em árvore de um grafo $G$ é uma árvore cujos nós são rotulados com conjuntos de vértices de $G$ ; esses conjuntos são chamados de bolsas. Para cada vértice $v$ , os sacos que contêm $v$ devem induzir uma subárvore da árvore, e para cada aresta $uv$ deve existir um saco que contém $u$ e $v$ . A largura da decomposição de uma árvore é um a menos que o número máximo de vértices em qualquer um de seus sacos; o treewidth de $G$ é a largura mínima de uma decomposição árvore da $G$ .
largura da árvore: O treewidth de um gráfico que $L$ é a largura mínima de uma árvore de decomposição $L$ . Ele também pode ser definida em termos do número de clique de um conclusão cordal de $G$ , o fim de um refúgio de $L$ , ou o fim de um espinheiro de $L$ .
triângulo: Um ciclo de três comprimentos em um gráfico. Um gráfico sem triângulo é um gráfico não direcionado que não possui subgráficos de triângulo.
Turán: 1. Pál Turán; 2. Um gráfico Turán é um gráfico multipartido completo balanceado.; 3. O teorema de Turán afirma que os grafos de Turán têm o número máximo de arestas entre todos os grafos livres de cliques de uma determinada ordem.; 4. O problema da fábrica de tijolos de Turán pede o número mínimo de travessias em um desenho de um grafo bipartido completo.

você

não direcionado: Um gráfico não direcionado é um gráfico no qual os dois pontos finais de cada aresta não são distinguidos um do outro. Veja também dirigido e misto . Em um gráfico misto , uma aresta não direcionada é novamente aquela em que os pontos finais não são distinguidos uns dos outros.
uniforme: Um hipergrafo é $k$ -uniforme quando todas as suas arestas têm $k$ pontos finais, e uniforme quando é $k$ -uniforme para algum $k$ . Por exemplo, gráficos comuns são iguais aos hipergrafos $2-$ uniformes.
universal: 1. Um gráfico universal é um gráfico que contém como subgráficos todos os gráficos de uma determinada família de gráficos ou todos os gráficos de um determinado tamanho ou ordem dentro de uma determinada família de gráficos.; 2. Um vértice universal (também chamado de vértice ou vértice dominante) é um vértice adjacente a todos os outros vértices do gráfico. Por exemplo, gráficos de roda e gráficos de limiar conectados sempre têm um vértice universal.; 3. Na lógica dos gráficos , um vértice universalmente quantificado em uma fórmula pode ser chamado de vértice universal dessa fórmula.
gráfico não ponderado: Um gráfico cujos vértices e arestas s não receberam peso s ; o oposto de um gráfico ponderado .

V

V: Veja conjunto de vértices .
valência: Sinônimo de diploma .
vértice: Um vértice (vértices plurais) é (junto com as arestas) uma das duas unidades básicas com as quais os gráficos são construídos. Os vértices dos gráficos são frequentemente considerados objetos atômicos, sem estrutura interna.
corte de vértice
conjunto de separação: Um conjunto de vértices cuja remoção desconecta o gráfico . Um corte de um vértice é chamado de ponto de articulação ou vértice de corte .
conjunto de vértices: O conjunto de vértices de um dado grafo $G$ , às vezes denotado por $V (G)$ .
vértices: Veja vértice .
Vizing: 1. Vadim G. Vizing; 2. Teorema de Vizing de que o índice cromático é no máximo um a mais que o grau máximo.; 3. Conjectura de Vizing sobre o número de dominação dos produtos cartesianos dos gráficos.
volume: A soma dos graus de um conjunto de vértices.

C

$C$: A letra $W$ é usada em notação para gráficos de rodas e gráficos de moinhos de vento . A notação não é padronizada.
Wagner: 1. Klaus Wagner; 2. O gráfico de Wagner , uma escada Möbius de oito vértices.; 3. Teorema de Wagner caracterizando grafos planares por seus menores proibidos.; 4. Teorema de Wagner que caracteriza os grafos $K 5$ -menores livres.
andar: Um passeio é uma sequência finita ou infinita de arestas que se junta a uma sequência de vértices . As caminhadas às vezes também são chamadas de correntes . Uma caminhada é aberta se seu primeiro e último vértices forem distintos e fechada se forem repetidos.
fracamente conectado: Um gráfico direcionado é denominado fracamente conectado se a substituição de todas as suas arestas direcionadas por arestas não direcionadas produzir um gráfico conectado (não direcionado).
peso: Um valor numérico, atribuído como um rótulo a um vértice ou borda de um gráfico. O peso de um subgrafo é a soma dos pesos dos vértices ou arestas dentro desse subgrafo.
gráfico ponderado: Um gráfico cujos vértices ou arestas s receberam peso s ; mais especificamente, um gráfico com peso de vértice tem pesos em seus vértices e um gráfico com peso em arestas tem pesos em suas arestas.
bem colorido: Um gráfico bem colorido é um gráfico cujas cores gananciosas usam o mesmo número de cores.
bem coberto: Um gráfico bem coberto é um gráfico cujos conjuntos independentes máximos têm o mesmo tamanho.
roda: Um gráfico de roda é um gráfico formado pela adição de um vértice universal a um ciclo simples.
largura: 1. Um sinônimo de degenerescência .; 2. Por outras invariantes gráfico conhecidos como largura, ver a largura de banda , branchwidth , bando de largura , largura de caminho , e treewidth .; 3. A largura de uma decomposição em árvore ou decomposição de caminho é um menor que o tamanho máximo de um de seus sacos e pode ser usada para definir a largura da árvore e a largura do caminho.; 4. A largura de um gráfico acíclico direcionado é a cardinalidade máxima de uma anticadeia.
moinho de vento: Um grafo de moinho de vento é a união de uma coleção de cliques, todos da mesma ordem entre si, com um vértice compartilhado pertencente a todos os cliques e todos os outros vértices e arestas distintos.

Languages

In other projects

Glossário de teoria dos grafos - Glossary of graph theory

Símbolos

UMA

B

C

D

E

F

G

H

eu

K

eu

M

N

O

P

Q

R

S

T

você

V

C

Veja também

Referências