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