Aulamo405_20110912_automorfismo

Referencias Automoformos - Hansay - grupos Decomposicoes A decomposicao de um grafo G e uma familia F de subgrafos de G disjuntos nas arestas tal que U F,E(Fi) = E(G) Fi F 1) F1 v1 v2 v4 F2 v3 F3 v5 v1 2) decomposicao por caminhos Este grafo possui uma decomposicao por caminhos G nao e simples, e tem loops v2 v1 v2 v5 v4 OK 2 4 D - e nao e 2 caminho F v3 v5 v2 v3 v1 Ex. 2 K4 V4 v8 v8 v7 v1 v2 v6 - Decomposicao por copias de P3 K5 K5 admite uma decomposicao com 2 copias de C3 - Decomposicao em ciclos Kn = G U G ando |V(G)| = n K7 v2 v3 v4 v4 v5 12/09 2 G v3 v1 v3 G v1 v3 Auto-complementar, G = G Um grafo e auto-complementar se e somente se Kn admite duas copias de G numa decomposicao em 2 copias de G G tal que |V (G)| = n. G auto-complementar, entao G G. Como G U G Kn => Kn admite uma decomposicao em 2 copias de G + Kn = G U G + G Dado G uma familia F = {F1, F2, ..., Fn} que e uma decomposicao, entao G = U Fi 1 = 1 (Ex. a) Decomposicao em 3 copias de P4 b) G e 3-auto em 4 copias de K1,3 c) G admite uma decomposicao em copias de H, entao m(G) m (H) F1, F2, F3, H1, H2, ..., HK H1 H m(G) = m(H) Decomposicao de Kn em copias de K3 v2 v1 v2 vi m (Kn) = 6 dendo 3 G4 v3 Suponha que G admite uma decomposicao com copias de K3 logo v E V(G) Entao cada aresta incidente a v pertence exatamente a um K3: Alem disso G tem e 2 disjuntos nas aresta. logo, d(vi) par. Demos v arbitrario, v V(G), d(v) par Grafo par é um grafo onde todo vértice tem grau par. 12/09 3 Se G admite uma decomposição em cópias de K3, então V E V(G), d(V) par. K5 – não – grafo par m(K5) = 10 10/3 K5 não admite uma decomposição em cópias de K3 K4 – não – grafo par m(K4) = 21/3 surprising!! notas rabras não “perda preta 0” 1 1 1 1 1 0 2 Discompor K5, K6, K9 em cópias de G, G C0, respectivamente Decomposição em ciclos Detetar grafos que não possuem decomposição em ciclos 2) Se G tem uma decomposição em ciclos, então E V(G), d(v) par. 2) G par, então G tem uma decomposição em ciclos? K5 v7 v2 v5 v3 v9 h12: G u G2 U Gc v8 v4 v1 v4 v1 v1 v1 v7 Indução em m / G: par base: m=0; então F ϕ é uma decomposição de G. H.I. Suponha que para todo grafo G par com O(m) n0, G tem uma decomposição em ciclos Prove: Seja G um grafo par, com m arestas => E(G) \/= \phi, entao pode 12/09 (4) não connexarith G tal que d_H(V) >= 2 v V € V(H). Logo H contém um ciclo C. (proceda sem autos) . m(H) < m(H) . H^2 por , Dia flahe: seja v € V(H+1), fantao eu V € V(C) ou v f V(C) + eu f V(C) => d_H(v) = d_H(v) + a o V(C) => d_H(v) = d_H(v) - 2 Logo v € V(H) = d_H(v) = par => H+2 grafo par . logo por H_1, H_1 admite uma descomposicao frn ciclos . Portanto P U {C}: = uma descomposicao em ciclo de G. Tes : Um grafo G admite uma descomposicao em ciclo se G é par.