Demostracions de Teoria de Grafs: Problemes i Solucions

Demostracions de Teoria de Grafs

Proveu que en tot graf el número de vèrtex amb grau senar ha de ser parell:

Sigui CVGp el conjunt de vèrtex de grau parell i CVGs el conjunt de vèrtex de grau senar respectivament. Per contradicció, suposarem que CVGs té un número senar de nodes, amb la qual cosa, si sumem els seus graus obtenim un número senar. Si ara sumem els graus de CVGp obtenim un número parell. Per tant, si sumem els graus de tots dos obtenim un número senar, la qual cosa és impossible.

Sigui G un graf amb n nodes. Proveu que si tot vèrtex de G té grau n/2 o superior, aleshores G és connex:

Per contradicció, suposarem que G no és connex, per tant, té com a mínim 2 components connexos. Si C1, C2, ..Ck són els seus components connexos ordenats per mida creixent i m=|V1|. Així doncs m <= n/2. Però |V1| + |V2| > n/2 + n/2 = n, la qual cosa és impossible. El grau de cada vèrtex de V1, és per tant, com a molt m - 1 <= n/2 - 1, contradicció.

Sigui G un graf qualsevol que conté dos nodes, anomenats x i y, amb grau senar i la resta amb grau parell. Proveu que hi ha un camí que connecta x amb y.

Per contradicció. Suposem que no hi ha cap camí que connecta X amb Y. Sigui Cc el component connex que conté X. Observem que la resta de nodes de Cc tenen grau parell (ja que Y no pot estar a Cc). Però és impossible que en un graf hi hagi exactament un node de grau senar.

Kuratowski K3,3 i K5:

Un graf G és planar si i només si no conté cap subdivisió K3,3 o K5.

Si un graf conté una subdivisió K3,3, cal que tingui, com a mínim, 6 vèrtex amb grau 3 o superior. Si un graf conté una subdivisió K5, cal que tingui, com a mínim, 5 vèrtex amb grau 4 o superior. Tant K3,3 com K5 tenen vèrtex de grau 3. Per tant, qualsevol subdivisió d’ells també contindrà vèrtex amb grau 3 o superior. Per tant, si un graf G conté una subdivisió de K3,3 o K5 ha de contenir com a mínim un vèrtex amb grau 3 o superior.

Proveu que si tots els vèrtexs d’un graf G tenen grau 2 o inferior, aleshores és planar:

Si un graf no és planar, aleshores, segons el Teorema de Kuratowski, conté un subgraf que és isomorf a una subdivisió de K5 o K3,3. Tant K3,3 com K5 tenen vèrtex de grau 3. Per tant, qualsevol subdivisió d’ells també contindrà vèrtex amb grau 3 o superior. Per tant, si un graf G conté una subdivisió de K3,3 o K5 ha de contenir com a mínim un vèrtex amb grau 3 o superior.

Sigui G un graf amb nodes x1,...,xn, sigui M la seva matriu d’adjacència i sigui N = M · M. Sigui Xi i Xj vèrtexs qualsevol (no necessàriament diferents) de G. Proveu que Ni,j és exactament el número de passeigs de longitud 2 on el vèrtex d’inici és Xi i el vèrtex final és Xj:

Un passeig de longitud 2 amb V. inicial Xi i V. final Xj té la forma Xi, Xk(1), Xj(2), on Xk ha de ser un vèrtex adjacent a Xi i Xj. Per tant, si volem saber el número de passeigs de mida 2 de Xi a Xj en tenim prou amb comptar quants vèrtex hi ha adjacents a Xi i Xj simultàniament.

El valor de Ni,j per definició de producte de matrius serà:

Ni,j = Mi,1·M1,j + Mi,2·M2,j + … + Mi,n·Mn,j

El terme K-èsim de la suma anterior Mi,k·Mk,j val 1 precisament si Mi,k i Mk,j valen tots dos 1 o, el que és el mateix, si Xk és adjacent a Xi i Xj. Ni,j conta el número de vèrtexs adjacents a Xi, Xj.

Proveu que tot arbre és bipartit:

Sigui T un arbre i sigui X un vèrtex qualsevol de T. Sigui Cx el conjunt de tots els nodes que es troben a distància parell de X i sigui Cy el conjunt de nodes que es troben a distància senar de Y. Anem a veure que (Cx, Cy) és una bipartició de T. Sigui e = {y, z} una branca de T. Podem suposar que dist(x, z) = dist(x, y) + 1, per tant y i z es troben en conjunts diferents.