Lista 1 Teoria dos Grafos

Prévia do material em texto

Teoria dos Grafos
Lista de exercicios 01
Wallyson Carvalho Soares
Sim, pois contém o mínimo de arestas de para formar uma árvore geradora que são arestas, onde é o número total de vértices de . Com a remoção de um vértice em que possui grau maior do que 1 essa propriedade não será cumprida, pois terá menos arestas do que o necessário.
Sim, se este vértice é um vértice de corte em é porque sua ausência gera uma componente conexa a mais que , assim, este vértice pode ser o intermediário que mantém o grafo conexo, então este vértice continua mantendo o grafo todo conexo na árvore geradora de .
Não, pois a remoção do um nó folha não compromete a propriedade de árvore. Esta sempre se manterá consistente, não dividida.
Se um grafo possui apenas um vértice já podemos ver que é formado uma árvore e a sua prova é trivial. Por indução, supomos que a afirmação é verdadeira e toda árvore com vértices possui arestas, com . Acrescentamos um vértice ao grafo que representa a árvore e podemos ver que sem o acréscimo de uma aresta não seria possível a formação de uma árvore, mas de uma floresta. Logo, temos que acrescentar uma aresta, e apenas uma, que ligue a outro vértice da árvore para manter a propriedade de árvore. Se adicionarmos outra aresta que ligue a outro vértice teremos um ciclo, deixando de ser uma árvore. Assim, podemos ver neste exemplo que ao acrescentarmos um vértice a uma árvore de vértices e arestas, mantendo a propriedade de árvore, teremos uma árvore com vértices e arestas.
Suponha que T seja um subgrafo conexo de G com todos os vértices de G e apenas um caminho ligando estes vértices(uma árvore). Se pegarmos qualquer dois vértices u e v em T e adicionarmos mais um caminho entre estes vértices T deixaria de ser uma árvore, pois esse novo caminho geraria um ciclo, ou seja, existe apenas um caminho entre os vértices de T; no entanto, como em T existe apenas um caminho entre dois vértices, a retirada de uma aresta do caminho que liga estes dois vértices geraria um grafo desconexo(uma floresta).
Suponha um subgrafo conexo minimal e um vértice qualquer . Se removermos o vértice de o grafo seria desconexo, ou seja, não poderia ser também um árvore geradora pois tal grafo seria uma floresta.
Seja o vértice , com grau . Se removermos este vértice, deixará de ser uma árvore e será uma floresta com árvores , onde que cada uma dessas árvores eram vizinhos de na árvore . Caso uma dessas árvores geradas consistir de apenas um vértice, então essa árvore certamente era uma folha em ; caso contrário essa árvore possui, pelo menos, duas folhas que não são vizinhas de , sendo assim folhas de .
 
Sendo um grafo direcionado, existe uma ligação direcionada de um vértice para um vértice , com , sendo que nenhum caminho bidirecional existe neste grafo. Assim, como sabemos que um arco que sai de um vértice sempre chega em outro podemos dizer que cada arco sai e chega em um vértice ao mesmo tempo, sendo possível afirmar que , ou seja, o somatório dos arcos que saem de cada vértice de gera a mesma quantidade do somatório dos arcos que chegam nos vértices de . Então, sendo o conjunto dos arcos do grafo podemos afirmar que:
			
	 = vértices que saem de um vértice .
 = vértices que chegam em um vértice .
 = número total de arestas que saem dos vértices de .
 = número total de arestas que chegam nos vértices de .
 = conjunto de arcos do grafo .
	
Montando uma matriz podemos ver que a quantidade de elementos úteis em cada linha(), ou seja, acima da diagonal principal, vai decrementando em um do tamanho da dimensão da matriz(), sendo este decremento acumulado a medida que descemos nas colunas da matriz. Na última linha, ou quando , resta apenas um elemento da diagonal principal, sendo este não incluído entre os elementos úteis. Assim, podemos ver que serão incluídos no vetor apenas os elementos até a linha e podemos escrever a equação como:
		
Implementações serão enviadas em anexo.
	unsigned int vizinho(unsigned int *m, unsigned int u, unsigned int v){
 unsigned int ele = 0;
 if(u < v)
 ele = (u*n) + v - (((u+1)+(u+2))/2);
 else if(u > v)
 ele = (v*n) + u - (((v+1)+(v+2))/2);
 return ele;
}
	
	 é um subgrafo induzido por um conjunto de vértices se e vale a seguinte propriedade, sendo e vértices: 
 se ∈ e ∈ então ∈ .
Para sabermos a quantidade de subgrafos podemos utilizar a combinação simples para encontrarmos todas as possibilidades de combinar os vértices de ; levando em conta as quantidades de vértices possíveis em cada subgrafo. Assim, temos:
onde é a quantidade de vértices que o subgrafo terá e é o número total de vértices de .
ANULADA
A expressão para os subgrafos geradores de pode se dar pela combinação de todas as arestas de sobre todos os vértices de . Sendo que qualquer que seja esse subgrafo, como é gerador de , ele terá todos os vértices de .
onde é a quantidade de arestas que o subgrafo terá e é o número total de arestas de .
O número de subgrafos de G será dado pela combinação de todos os vértices com todas as possíveis combinações de arestas que ligam estes vértices. Assim ,temos:
onde que 
nos dá a combinação de todos os vértices, como na 
questão a., e as possibilidades de ter ou não arestas no conjunto de vértices .
Implementações serão enviadas em anexo.
Primeiro provaremos, por indução, que toda aresta em um árvore é uma ponte depois, a partir desta prova, provaremos que o conjunto de componentes conexas de sem o vértice é igual ao grau do vértice :
Supondo que uma aresta na árvore não é uma ponte então existem, pelo menos, dois vértices e em que estão ligados por dois caminhos distintos e . No entanto, e geram um ciclo em , o que não pode ocorrer pois violaria a definição de árvore;
Assim, pelo item anterior, podemos afirmar que toda aresta em uma árvore é uma ponte, sendo que ao retirarmos as arestas conectadas a um vértice , , o grafo passaria a ter componentes conexas, ou seja:
			
	 = conjunto de componentes conexas de ;
	= grau do vértice que está no grafo .
	
A ideia dessa busca e começar por um vértice e pesquisar pelo grafo em todas as direções nível por nível, visitando primeiro os vértices vizinho de ( que terão distancia 1 de ) e depois os vértices vizinhos dos vizinhos de , que terão distancia 2 de , e assim por diante. Assim, podemos ver que se temos um vértice a uma distância este terá um vizinho a uma distância . Então, se temos um vértice a uma distância também teremos os vértices vizinhos a distância .
Caracterize:
Árvore em largura:
Visita primeiro os vértices mais próximos da raiz de busca antes de visitar os mais distantes;
A árvore geradora é uma árvore com mais larga;
A solução encontrada primeiro será a de menor profundidade;
Melhor para soluções que estão mais próximas da raiz.
Árvore em profundidade:
Explora completamente um ramo da árvore antes de ir ao ramo vizinho;
Altura da árvore bem maior que da árvore em largura, maior profundidade;
Melhor para soluções que se encontram perto dos vértices folha.
	Vértices de corte é o conjunto dos vértices no qual a remoção de qualquer um destes vértices torna desconexo e provoca um aumento na quantidade de componentes conexas de . Arestas de corte, ou Pontes, geram os mesmos resultados do que os vértices de corte, porém a remoção é aplicada nas arestas de .	Comment by wallyson soares: como descobrir ? tem algum algoritmo ?
No grafo do item a temos c, d, e, f, h, i, j como vértices de corte, pois a remoção de qualquer um destes resultaria no aumentos de componentes conexas do grafo.Se virmos este grafo como uma árvore podemos perceber que os vértices a e b são folhas, onde que a remoção destas não violaria as propriedades de árvore.
No que se diz respeito a remover uma aresta, como o grafo é uma árvore em profundidade, ou seja, uma árvore geradora mínima,todas as arestas deste grafo são uma ponte, pois a remoção de qualquer uma geraria, no mínimo, duas componentes conexas no grafo.
 Suponhamos a raiz de e vértice de corte em . Se removermos então cada componente de tem que ter um filho de . Se é vértice de corte, então possui mais de um componente e então possui mais de um filho em ; caso contrário teria um ciclo e não teria outro filho. 
 Suponha que é vértice de corte de e possui dois filhos e que têm descendentes e , respectivamente. Se existisse um vértice antecessor de ambos e o grafo teria um ciclo e as adjacências de e seriam exploradas antes das adjacências de e , que por sua vez teria as adjacências exploradas antes do vértice , ou seja, quando for a vez de explorar suas adjacências apenas uma delas teria sido explorada, pois a outra teria sido explorada por conta do ciclo em , e se tivesse este ciclo não seria vértice de corte.
	Comment by wallyson soares: teria um caminho alternativo de se chegar aos "filhos de r" e outros vertices iriam explorar eles antes de r
 Seja um vértice de corte em que não é raiz de e seja o pai de . Assim, o vértice tem que ter um filho em para que e pertencem a componentes diferentes em . Suponha que tem um filho que é vizinho de um ancestral de , que chamaremos de . Neste caso, o caminho seria um caminho de a em , e não seria vértice de corte.
 Agora, seja descendente de (não raiz de ) e também descendente de em ; sendo ancestral próprio de . Neste caso podemos observar que existiriam dois caminhos diferentes ao conjunto representado pelo vértice e com a remoção de ou (se não fosse raiz) não tornaria desconexo.
 Seja uma aresta de corte em , supondo que é pai de em e, utilizando o item anterior, podemos dizer que é vértice de corte em , assim a aresta que ligaria à seria uma ponte e a única ligação entre as componentes representadas por e então podemos afirmar que .
 Seja pertencente às arestas de tal que nenhuma aresta de ligue um descendente de a um ancestral de . Se houvesse um caminho em ainda existiria uma aresta em que ligaria u a v.