Lista 11 - grafos

Prévia do material em texto

Grafos - Sec¸o˜es 9.1 e 9.2
1) Quantos ve´rtices e quantas arestas tem Kn? Cn? Wn? Qn?
2) Demonstre que 2|E| =∑v∈V d(v).
3) Demonstre que todo grafo tem um nu´mero par de ve´rtices de grau ı´mpar.
4) Cn e´ subgrafo de Wn?
5) Cn e´ subgrafo de Cn+1?
6) C4 e´ subgrafo de Wn?
7) Qn e´ subgrafo de Qn+1?
8) Kn e´ subgrafo de Kn+1?
9) K3 e´ subgrafo de Kn?
10) K3 e´ subgrafo de Kn do qual foi removida uma aresta?
11) Cn e´ subgrafo de Kn?
12) Wn e´ subgrafo de Kn+1?
13) Qn e´ subgrafo de Kn?
14) Falso ou verdadeiro?
(a) Num grupo de 7 pessoas e´ possivel que cada uma conhec¸a exatamente 3 outras.
(b) Se um grafo conexo com pelo menos 3 ve´rtices tem o mesmo nu´mero de ve´rtices e de arestas,
enta˜o ele e´ um ciclo.
15) Considere um grafo G = (V,E). Nesta questa˜o, vamos explorar as definic¸o˜es de grafos usando
s´ımbolos lo´gicos. Por exemplo, aqui esta´ a definic¸a˜o de G ser bipartido:
∃V1, V2 : (V1 ∪ V2 = V ) ∧ (V1 ∩ V2 = ∅) ∧ ∀{a, b} ∈ E : (a ∈ V1 ∧ b ∈ V2) ∨ (a ∈ V2 ∧ b ∈ V1).
(a) Escreva usando s´ımbolos lo´gico a definic¸a˜o de G ser o grafo bipartido completo Kn,m.
(b) Escreva a definic¸a˜o de G ser um grafo com uma ponte.
(c) Escreva a definic¸a˜o de G ser o grafo roda Wn.
(d) Escreva a definic¸a˜o de G ser o grafo completo Kn.
(e) Seja d(v) o grau do ve´rtice v, ou seja, quantas arestas incidem nele. Escreva a definic¸a˜o de
d(v) ≥ 2.
(f) Esta definic¸a˜o de G ser o grafo c´ıclico Cn esta´ certa ou errada? Justifique.
∀v : d(v) = 2
1
16) Considere a definic¸a˜o abaixo:
∀i, j ∈ N : (i ≤ n ∧ j ≤ n)↔ (i, j) ∈ V
∧∀u = (iu, ju), v = (iv, jv) ∈ V : {u, v} ∈ E ↔ (|iu − iv| = 1 ∨ |ju − jv| = 1)
a) Desenhe 3 grafos que seguem esta definic¸a˜o, para diferentes valores de n
b) Fac¸a uma pequena alterac¸a˜o a` definic¸a˜o para que ela inclua o seguinte grafo:
2