Embed Size (px)
Citation preview
Trabalho Computacional I:
Algoritmo de Teste de Planaridade
Professora: Maria Cláudia Boeres
Mestrando: Wilson Guasti Junior
Tópicos
• Descrição do problema
• Abordagem do problema
• Complexidade dos algoritmos
• Comparação dos resultados
• Conclusão
Descrição do Problema
• Teste de Planaridade:
• Determinar se um dado grafo pode ser desenhado no plano de tal forma que suas arestas só se intersectem nos pontos extremos
Abordagem do problema
• Script I
• Verificação da Planaridade de Grafos utilizando uma biblioteca exclusiva para o sistema Mathematica, a Combinatórica.
1 Script I
2
(* :Title: Verificação da Planaridade de Grafos utilizando uma biblioteca exclusiva para o
sistema Mathematica, a Combinatorica*)
3 w:=5;
4 Timing[
5 PlanarQ[RandomGraph[w,0.5]]
6 ]
Abordagem do problema
• Script I
1 PlanarQ[g_Graph] :=
2 Block[{simpleGraph = MakeSimple[g],
3 $RecursionLimit = Infinity},
4 SimplePlanarQ[simpleGraph]
5 ]
6
7 SimplePlanarQ[g_Graph] :=
8 Module[{components, $RecursionLimit = Infinity},
9 components = BiconnectedComponents[g];
10 Apply[ And,
11 Map[(PlanarQ[InduceSubgraph[g,#]])&, components]
12 ]
Abordagem do problema
• Script I
13 ] /; !(ConnectedQ[g] && BiconnectedQ[g])
14
15
BiconnectedComponents[g_Graph] := First[FindBiconnectedComponents[g]] /; UndirectedQ[g]
16 FindBiconnectedComponents[g_Graph] := { {}, {} } /; EmptyQ[g]
17
18 FindBiconnectedComponents[g_Graph] :=
19
20 Map[(SearchBiConComp[First[#]]) &, Select[cc = ConnectedComponents[g], Length[#] > 1 &]];
21 {Join[bcc, Select[cc, Length[#] == 1 &]], Drop[ap, -1]}
22
]
23
24
Abordagem do problema
• Script I
1 Script I(grafos densos)
2
(* :Title: Verificação da Planaridade de Grafos utilizando uma biblioteca exclusiva para o sistema Mathematica, a
Combinatorica*)
3 w:=100
4 e:= (w*(w-1))/2
5 d :=2*e/w*(w-1)
6 Timing[
7 PlanarQ[ExactRandomGraph[w,d]]
8 ]
Abordagem do problema
• Script I
1
Script I (Grafos Sparsos)
2
(* :Title: Verificação da Planaridade de Grafos utilizando uma biblioteca exclusiva para o sistema
Mathematica, a Combinatorica*)
3 w:=5;
4
Timing[
5
PlanarQ[RandomGraph[w,0.1]]
6
]
Abordagem do problema
• Script II
• Verificação da Planaridade de Grafos utizando o Teorema de Kuratowski .
Abordagem do problema
• Script II
• Verificação da Planaridade de Grafos utizando o Teorema de Kuratowski .
1 Script II
2
(* :Title: Verificação da Planaridade de Grafos utizando o Teorema de Kuratowski *)
3 w:=50;
4 Timing[
5 j:=CompleteGraph[5];
6 k:=CompleteGraph[3,3];
7 h:=RandomGraph[w,0.5];
8 IsomorphicQ[j,h]||IsomorphicQ[k,h]
Abordagem do problema
• Script II
1 Script II (grafos densos)
2
(* :Title: Verificação da Planaridade de Grafos utizando o Teorema de Kuratowski *)
3 w:=100
4 e:= (w*(w-1))/2
5 d :=2*e/w*(w-1)
6 Timing[
7 j:=CompleteGraph[5];
8 k:=CompleteGraph[3,3];
Abordagem do problema
• Script II
1 Script II (Grafos Sparsos)
2
(* :Title: Verificação da Planaridade de Grafos utizando o Teorema de Kuratowski *)
3 w:=50;
4 Timing[
5 j:=CompleteGraph[5];
6 k:=CompleteGraph[3,3];
7 h:=RandomGraph[w,0.1];
8 IsomorphicQ[j,h]||IsomorphicQ[k,h]
9 ]
Complexidade dos Algoritmos
• Examinamos estes algoritmos, eficientes, quanto `a forma como caracterizam planaridade, foi evidenciado que eles proporcionam complexidade linear aos problemas.
Tabela comparativa I: Grafos Esparsos
Número de vértices
Tempo em segundos
Script I (Lib Combinatóric
a)
Script II (Kuratowski)
Resultado
50
0.016
0.031
True
100
0.047
0.078
True
200 0.156
0.249
True
300 0.327
0.609
True
500 0.92
1.731
True
Tabela comparativa II: Grafos Esparsos
Número de vértices
Tempo em segundos
Script I (Lib Combinatóric
a)
Script II (Kuratowski)
Resultado
50
0.015
0.031
True
100
0.046
0.078
True
200 0.156
0.25
True
300 0.327
0.593 True
500 0.968
1.716
True
Tabela comparativa I: Grafos Densos
Número de vértices
Tempo em segundos
Script I (Lib Combinatóric
a)
Script II (Kuratowski)
Resultado
50
0.53 0.062
False
100
1.17
0.156
False
200 5.085
0.655
False
300 11.217
1.466
False
500 31.341
3.9
False
Tabela comparativa II: Grafos Densos
Número de vértices
Tempo em segundos
Script I (Lib Combinatóric
a)
Script II (Kuratowski)
Resultado
50
0.374
0.047
False
100
1.201
0.171
False
200 5.413
0.655
False
300 11.31
1.451
False
500 33.025
3.994
False
Tabela comparativa: Grafos Completos
Número de vértices
Tempo em segundos
Script I (Lib Combinatóric
a)
Script II (Kuratowski)
Resultado
50
0.187
0.047
False
100
0.749
0.156
False
200 3.042
0.499
False
300 2.637
1.139
False
500 1.872
3.229
False
Conclusão
• Muito embora, os algoritmos utilizados nos scripts tenham resultado semelhante em boa parte dos casos, o que faz uso do Teorema de Kuratowski manteve o crescimento de tempo menos acentuado a medida que o número de vértices aumentou.
