Proposta:

Definir a classe Grafos composta numa matriz adjacente.

class grafo {

int qtde; //QTD de nós
int *v; //Vetor peso
int **m; //Matriz de Adjacencia
int i,j;

public:

void madj(){
qtde=0;
v=NULL;
m=NULL;
}
void madj(int tam){
qtde=tam;
v= new(int[tam]);
*m=new(int[tam);

for(i=0;i< i="0;i<" j="0;j<">

MATRIZ DE ADJACÊNCIA

A matriz de adjacência é uma matriz de N x N (onde N é o número de vértices do grafo).

Ela inicialmente é preenchida toda com 0 e quando há uma relação entre o vértice do x (número da coluna)
com o do y (número da linha), matriz[x][y] é marcado um 1.


A matriz de adjacência mostra o relacionamento entre os nós de um grafo.

Se um nó a for adjacente a um nó b, então na matriz de adjacência M as entradas M[a,b]
e M[b,a] serão diferentes de 0.

O valor armazenado nestas entradas indicarão a quantidade de arestas existentes entre os vértices a e b.

Matriz Adjacente:

GRAFOS

O artigo de Leonhard Euler, publicado em 1736, sobre o problema das Sete Pontes de Königsberg, é considerado o primeiro resultado da teoria dos grafos. É também considerado um dos primeiros resultados topológicos na geometria; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e topologia.

Ponte de Konigsberg e a sua Representação Gráfica feita por Euler.

Um grafo é um conjunto de pontos, chamados vértices (ou nodos ou nós), conectados por linhas, chamadas de arestas (ou arcos).

Um grafo com 6 vértices e 7 arestas.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio. Se as arestas têm uma direção associada (indicada por uma seta na representação gráfica) temos um grafo direcionado, ou dígrafo.

Nós = { A, B, C, D, E, F, G, H }
Arcos: E = {(A,A), (A,B), (A,C), (A,D), (C,D), (C,F), (E,G)}

Um grafo com um único vértice e sem arestas é conhecido como o grafo trivial ou "o ponto".

Conceitos básicos de Teoria dos Grafos

Um laço (loop) num grafo ou num digrafo é uma aresta e em E cujas terminações estão no mesmo vértice. Um digrafo ou grafo é chamado simples se não tem laços e existe no máximo uma aresta entre quaisquer dois vértices.

Exemplo de Grafo

O grafo acima é um grafo simples com o conjunto de vértices V = {1, 2, 3, 4, 5, 6} e um conjunto de arestas E = {(1,2), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6)}.

Uma aresta conecta dois vértices; esses dois vértices são ditos como incidentes à aresta.

A valência (ou grau) de um vértice é o número de arestas incidentes a ele, com loops contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. Se E é finito, então a valência total dos vértices é o dobro do número de arestas.

Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de um vértice) e o grau de entrada (o número de arestas entrando em um vértice). O grau de um vértice é igual à soma dos graus de saída e de entrada.

Dois vértices são considerados adjacentes se uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjascentes, mas os vértices 2 e 4 não são. O conjunto de vizinhos de um vértice consiste de todos os vértices adjascentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5. Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.

Na computação, um grafo finito direcionado ou não-direcionado (com, digamos, n vértices) é geralmente representado por sua matriz de adjacência: uma matriz n-por-n cujo valor na linha i e coluna j fornece o número de arestas do i-ésimo ao j-ésimo vértices.

Um caminho é uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete. O comprimento do caminho é o número de arestas que o caminho usa, contando-se arestas múltiplas múltiplas vezes. O custo de um caminho num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são independentes se não tiverem nenhum vértice em comum, excepto o primeiro e o último.

No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.

Se for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo, diz-se que o grafo é conexo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de remover k-1 vértices, então diz-se que o grafo está k-conexo. Note que um grafo está k-conexo se, e somente se, contém k caminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo.

Um ciclo (ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-se acíclico se não contém ciclos simples.

Uma árvore é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz.

Um subgrafo de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G.

Um grafo parcial de um grafo G é um subgrafo com o mesmo conjunto de vértices que G. Uma árvore parcial é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.

O grafo nulo é o grafo cujos conjuntos de vértices e de arestas são vazios.

Um conjunto independente em um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.