Simulacre d'examen de grafs i arbres

La cota.

$|E| \leq 3|V| - 6 = 3\cdot3 - 6 = 3$

D'on surt. De la fórmula d'Euler $|V| - |E| + |F| = 2$ i del fet que, en un graf simple, cada cara està limitada per almenys $3$ arestes i cada aresta toca com a molt $2$ cares. Això dona $2|E| \geq 3|F|$, i substituint a Euler surt la desigualtat.

Si a més el graf és bipartit, no hi pot haver cicles de longitud $3$ i cada cara necessita almenys $4$ arestes; la cota baixa a $2|V| - 4 = 2$.

Molt important: aquestes cotes són necessàries, no suficients. Si un graf les incompleix segur que no és planar; si les compleix, encara podria no ser-ho.

La cota.

$|E| \leq 3|V| - 6 = 3\cdot5 - 6 = 9$

D'on surt. De la fórmula d'Euler $|V| - |E| + |F| = 2$ i del fet que, en un graf simple, cada cara està limitada per almenys $3$ arestes i cada aresta toca com a molt $2$ cares. Això dona $2|E| \geq 3|F|$, i substituint a Euler surt la desigualtat.

Si a més el graf és bipartit, no hi pot haver cicles de longitud $3$ i cada cara necessita almenys $4$ arestes; la cota baixa a $2|V| - 4 = 6$.

Molt important: aquestes cotes són necessàries, no suficients. Si un graf les incompleix segur que no és planar; si les compleix, encara podria no ser-ho.

Pas 1 — comptar els graus senars. Als graus $[4, 4, 3, 3, 2]$ n'hi ha 2.

Pas 2 — aplicar el criteri. En un graf connex:

• Zero vèrtexs de grau senar: hi ha circuit eulerià, que torna al punt de partida.
• Exactament dos: hi ha recorregut obert, i ha de començar en un d'ells i acabar a l'altre.
• Més de dos: no hi ha cap recorregut que faci totes les arestes d'una tirada.

Amb 2 senars, la resposta és Recorregut eulerià obert.

Per què funciona. Cada vegada que passes per un vèrtex intermedi hi entres i en surts, o sigui que consumeixes dues arestes. Només els extrems del recorregut poden quedar descompensats, i n'hi ha com a molt dos.

Pas 1 — comptar els graus senars. Als graus $[5, 3, 2, 2]$ n'hi ha 2.

Pas 2 — aplicar el criteri. En un graf connex:

• Zero vèrtexs de grau senar: hi ha circuit eulerià, que torna al punt de partida.
• Exactament dos: hi ha recorregut obert, i ha de començar en un d'ells i acabar a l'altre.
• Més de dos: no hi ha cap recorregut que faci totes les arestes d'una tirada.

Amb 2 senars, la resposta és Recorregut eulerià obert.

Per què funciona. Cada vegada que passes per un vèrtex intermedi hi entres i en surts, o sigui que consumeixes dues arestes. Només els extrems del recorregut poden quedar descompensats, i n'hi ha com a molt dos.

La cota.

$|E| \leq 3|V| - 6 = 3\cdot12 - 6 = 30$

D'on surt. De la fórmula d'Euler $|V| - |E| + |F| = 2$ i del fet que, en un graf simple, cada cara està limitada per almenys $3$ arestes i cada aresta toca com a molt $2$ cares. Això dona $2|E| \geq 3|F|$, i substituint a Euler surt la desigualtat.

Si a més el graf és bipartit, no hi pot haver cicles de longitud $3$ i cada cara necessita almenys $4$ arestes; la cota baixa a $2|V| - 4 = 20$.

Molt important: aquestes cotes són necessàries, no suficients. Si un graf les incompleix segur que no és planar; si les compleix, encara podria no ser-ho.

La cota.

$|E| \leq 3|V| - 6 = 3\cdot14 - 6 = 36$

D'on surt. De la fórmula d'Euler $|V| - |E| + |F| = 2$ i del fet que, en un graf simple, cada cara està limitada per almenys $3$ arestes i cada aresta toca com a molt $2$ cares. Això dona $2|E| \geq 3|F|$, i substituint a Euler surt la desigualtat.

Si a més el graf és bipartit, no hi pot haver cicles de longitud $3$ i cada cara necessita almenys $4$ arestes; la cota baixa a $2|V| - 4 = 24$.

Molt important: aquestes cotes són necessàries, no suficients. Si un graf les incompleix segur que no és planar; si les compleix, encara podria no ser-ho.

Pas 1 — comptar els graus senars. Als graus $[1, 1, 1, 1]$ n'hi ha 4.

Pas 2 — aplicar el criteri. En un graf connex:

• Zero vèrtexs de grau senar: hi ha circuit eulerià, que torna al punt de partida.
• Exactament dos: hi ha recorregut obert, i ha de començar en un d'ells i acabar a l'altre.
• Més de dos: no hi ha cap recorregut que faci totes les arestes d'una tirada.

Amb 4 senars, la resposta és Cap de les dues.

Per què funciona. Cada vegada que passes per un vèrtex intermedi hi entres i en surts, o sigui que consumeixes dues arestes. Només els extrems del recorregut poden quedar descompensats, i n'hi ha com a molt dos.

La cota.

$|E| \leq 3|V| - 6 = 3\cdot20 - 6 = 54$

D'on surt. De la fórmula d'Euler $|V| - |E| + |F| = 2$ i del fet que, en un graf simple, cada cara està limitada per almenys $3$ arestes i cada aresta toca com a molt $2$ cares. Això dona $2|E| \geq 3|F|$, i substituint a Euler surt la desigualtat.

Si a més el graf és bipartit, no hi pot haver cicles de longitud $3$ i cada cara necessita almenys $4$ arestes; la cota baixa a $2|V| - 4 = 36$.

Molt important: aquestes cotes són necessàries, no suficients. Si un graf les incompleix segur que no és planar; si les compleix, encara podria no ser-ho.

El lema de les encaixades.

$\sum_{v} d(v) = 2|E|$

perquè cada aresta aporta $1$ al grau de cadascun dels seus dos extrems.

Aquí: la suma de graus és $4\cdot2 = 8$, i per tant

$|E| = \frac{8}{2} = 4$

La comprovació de paritat. La suma de graus sempre és parella. Si un enunciat et dona graus que sumen senar, aquell graf no existeix i no cal intentar dibuixar-lo. És una de les maneres més ràpides de descartar configuracions impossibles.

El resultat. Un arbre amb $14$ vèrtexs té exactament

$|E| = n - 1 = 13$

arestes.

Per què. Comença amb un sol vèrtex i cap aresta. Cada vegada que afegeixes un vèrtex nou l'has de connectar amb exactament una aresta: amb cap quedaria aïllat, i amb dues o més tancaries un cicle. Per tant, $14$ vèrtexs necessiten $13$ arestes.

Les dues cares del resultat. Connectar $14$ vèrtexs necessita com a mínim $13$ arestes; i un graf amb $14$ arestes o més sobre $14$ vèrtexs ha de tenir algun cicle. L'arbre és exactament el cas frontera.

El resultat. Un arbre amb $27$ vèrtexs té exactament

$|E| = n - 1 = 26$

arestes.

Per què. Comença amb un sol vèrtex i cap aresta. Cada vegada que afegeixes un vèrtex nou l'has de connectar amb exactament una aresta: amb cap quedaria aïllat, i amb dues o més tancaries un cicle. Per tant, $27$ vèrtexs necessiten $26$ arestes.

Les dues cares del resultat. Connectar $27$ vèrtexs necessita com a mínim $26$ arestes; i un graf amb $27$ arestes o més sobre $27$ vèrtexs ha de tenir algun cicle. L'arbre és exactament el cas frontera.

El lema de les encaixades.

$\sum_{v} d(v) = 2|E|$

perquè cada aresta aporta $1$ al grau de cadascun dels seus dos extrems.

Aquí: la suma de graus és $16\cdot4 = 64$, i per tant

$|E| = \frac{64}{2} = 32$

La comprovació de paritat. La suma de graus sempre és parella. Si un enunciat et dona graus que sumen senar, aquell graf no existeix i no cal intentar dibuixar-lo. És una de les maneres més ràpides de descartar configuracions impossibles.