). Nella soluzione del problema C5 del preIMO 2008, Gobbino (è lui, vero?) dice che si può dimostrare facilmente con double-counting che in un grafo i vertici da cui parte un numero dispari di lati sono per forza in numero pari. Come si può fare?Grafi e double-counting
Grafi e double-counting
Scusate la domanda forse stupidissima (di combinatoria non so molto... ). Nella soluzione del problema C5 del preIMO 2008, Gobbino (è lui, vero?) dice che si può dimostrare facilmente con double-counting che in un grafo i vertici da cui parte un numero dispari di lati sono per forza in numero pari. Come si può fare?
). Nella soluzione del problema C5 del preIMO 2008, Gobbino (è lui, vero?) dice che si può dimostrare facilmente con double-counting che in un grafo i vertici da cui parte un numero dispari di lati sono per forza in numero pari. Come si può fare?Edoardo
Praticamente ti conti la somma del numero di lati che esce da ciascun vertice al variare dei vertici, e così conti esattamente due volte(double counting) ciascun lato...quindi quella somma è pari(2 volte il numero di lati), quindi i vertici da cui esce un numero dispari di lati devono essere in numero pari.
Lo stolto è colui che dice quello che sa.Il saggio è colui che sa quello che dice.
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
"And then one day you find,ten years have got behind you,no one told when to run,you missed the starting gun"
-
Tibor Gallai
- Messaggi: 1776
- Iscritto il: 17 nov 2007, 19:12