Differences

This shows you the differences between two versions of the page.

--- lista:planares [2020/03/20 13:01]
lucas
+++ lista:planares [2020/03/25 11:47] (current)
lucas
@@ Line 14: / Line 14: @@
 {{ :lista:planaresexemplos.png?400 |}}
+**~~#~~** Mostre que um subgrafo de um grafo planar é um grafo planar.
 **~~#~~** Mostre que toda árvore com uma quantidade finita de vértices é planar.
@@ Line 37: / Line 39: @@
 **~~#.#~~** Conclua que o número de regiões de um grafo planar independe de sua representação planar.
-**~~#~~** Seja $G = (V,A)$ um grafo planar com uma quantidade finita de vértices. Se $|V|\geq 3$ e $|A|\geq 3$, observe que cada região é delimitada por pelo menos três arestas. Conclua que $|A|\leq 3|V|-G$.
+**~~#~~** Seja $G = (V,A)$ um grafo planar conexo com uma quantidade finita de vértices. Se $|V|\geq 3$ e $|A|\geq 3$, observe que cada região é delimitada por pelo menos três arestas. Conclua que $|A|\leq 3|V|-6$.
 **~~#.#~~** Mostre que $K_5$ não é um grafo planar.
+**~~#.#~~** Mostre que, se $G$ é um grafo planar conexo com menos de $12$ vértices, então $\delta(G) \leq 4$.
+**~~#.#~~** Mostre que, se $G$ é um grafo planar conexo, então $\delta(G)\leq 5$
 **~~#~~** Seja $G = (V,A)$ um grafo planar que não possui circuitos de três vértices como subgrafo. Se $V$ é finito, mostre que $|A|\leq 2|V|-4$.
+**~~#.#~~** Se $G$ é um grafo planar bipartido conexo, conclua que $\delta(G)\leq 3$.
+<WRAP tip>
+O problema abaixo é um quebra-cabeças clássico da matemática recreativa, conhecido como o **problema dos três serviços**.
+</WRAP>
+ **~~#~~** Abaixo temos a representação de três casas (A, B e C) que devem receber os abastecimentos de água (azul), eletricidade (amarelo) e gás (vermelho) através de canos conectando cada casa aos serviços necessários. É possível fazer essa conexão sem que haja cabos se cruzando?
+{{ :lista:casas.png?400 |}}
+<WRAP tip>
+O grafo que representa as conexões a serem feitas no problema dos três serviços é conhecido como $K_{3,3}$. Nessa lista, vimos que esse grafo, juntamente com o $K_5$, não é planar. Na realidade, em 1930, Kuratowski percebeu que todos os grafos não planares possuem $K_{3,3}$ ou $K_5$ como um tipo específico de subgrafo.
+</WRAP>

Combinando

User Tools

Site Tools

Differences

Page Tools