# Lista de termos técnicos relacionados à teoria dos grafos

Este glossário contém alguns termos técnicos relacionados com teoria dos grafos.

## A

* adjacent- adjacente
* adjacency matrix representation - representação de matriz de adjacência
* All-Pairs Shortest Paths (APSP) - não tenho visto tradução para este termo.
* adjacency matrix - matriz de adjacência
* adjacency list - lista de adjacência
* 2-coloring - bicoloração
* adjacent - adjacente
* augmenting - de aumento
* alternating - alternante
* almost every - quase todo

## B

* breadth-first - busca em largura
* bipartite - bipartido
* bipartition - bipartição
* bishop (in chess) - bispo (do xadrez)
* bridge - ponte

## C

* cage - gaiola
* chess - xadrez
* chromatic number - número cromático
* chromatic index - índice cromático
* circuit - circuito, ciclo
* claw - garra
* clique - clique
* clique number - cardinalidade de clique máxima
* coboundary - cofronteira, corte
* colorable - colorível
* coloring - coloração
* complete undirected graph - grafo não-dirigido completo
* connected - conexo
* cost - custo
* cut - corte, cofronteira
* cut edge - ponte
* cycle - ciclo, circuito
* cycle graph - grafo ciclo

## D

* degree - grau
* Depth-first - busca em profundidade
* diameter - diâmetro
* directed graph - grafo dirigido, grafo orientado ou grafo direcionado
* directed graph - digrafo (A palavra digrafo é horrível, mas é cômoda e corresponde bem ao termo digraph em inglês, que já está bastante arraigado. Alguns autores descuidados tornam as coisas ainda piores ao escrever "dígrafo", com acento; isso não faz sentido algum e deve ser evitado a todo custo.)

## E

* edge - aresta
* edge cover- cobertura de arestas
* eigenvalue - autovalor
* empty - vazio
* even - par

## F

* finite non-empty set - conjunto finito não vazio
* forest - floresta

## G

* girth - cintura
* graph - grafo
* graph reprentation - representação gráfica
* grid - grade

## H

* en:Hypergraph - hipergrafo

## I

* independence number - índice de estabilidade
* independent set- conjunto estável, conjunto independente
* indegree - grau de entrada
* induced - induzido
* isomorphic - isomorfo
* isomorphism - isomorfismo
* isthmus - ponte
* incident - incidente

## K

* king (in chess) - rei (do xadrez)
* knight (in chess) - cavalo (do xadrez)

## L

* length - comprimento
* line graph - grafo das arestas
* lower bound - delimitação (ou cota) inferior

## M

* matching - emparelhamento ou acoplamento
* matching number - cardinalidade de emparelhamento máximo
* maximal - maximal
* maximum - máximo
* minimal - minimal
* minimum - mínimo
* Minimum Cost Spanning Tree for Undirected Graphs - árvores geradoras de custo mínimo para grafos não dirigidos

## N

* neighbor - vizinho
* neighborhood - vizinhança
* null - vazio, nulo

## O

* odd - ímpar
* outdegree - grau de saída

## P

* path - caminho
* pawn (in chess) - peão (do xadrez)
* pivot - pivot
* polygon - circuito

## Q

* queen (in chess)- dama (do xadrez)

## R

* random graph - grafo aleatório
* rank - posto
* Related Concepts - conceitos relacionados
* rook (in chess) - torre (do xadrez)

## S

* spanning subgraph - subgrafo gerador
* stability number - índice de estabilidade (α)
* stable - estável
* star - estrela
* source - origem
* Shortest Path Problems for Directed Graphs - problemas de caminho mais curto para grafos dirigidos
* shortest path - caminho mais curto

## T

* tree - árvore
* two-colorable - bicolorível
* soft decision tree - "árvore de decisão difusa"

## U

* upper bound - delimitação (ou cota) superior
* undirected graph - grafos não dirigidos
* unordered - não ordenado

## v

* vertex - vértice
* vertex cover- cobertura de vértices

## W

* walk - passeio ou caminhada -- Uma caminhada é uma seqüência alternada de vértices e arestas, começando e terminando em um vértice, em que cada aresta é adjacente na seqüência de seus dois pontos finais. Num grafo orientado, a ordenação dos pontos de extremidade de cada aresta na sequência deve ser consistente com a direção da aresta. Algumas fontes chamam de trilha do caminho, enquanto outros reservam o termo "caminho" para um caminho simples (uma caminhada sem vértices ou arestas repetidas).
* weighted graph - grafo ponderado ou grafo valorado