Euler-féle poliédertétel Egy összefüggő síkbeli gráf, melynek n csúcsa, e éle és t tartománya van (beleértve a külső tartományt is), eleget tesz a következő formulának: n-e+t=2
Biz.: Ha van benne kör, akkor az a síkot két tartományra osztja. Hagyjunk el a körből tetszőleges élet, a gráf összefüggő marad. Az élek és a tartományok száma is eggyel csökken, n+t-e értéke nem változik. Ilyen lépésekkel az összes kört megszüntetve egy körmentes összefüggő gráfot, azaz fát kapunk (a gráf feszítőfája). Erre triviálisan igaz a formula, ugyanis t=1 és e = n-1.
Szerzők: yoda
[Szócikk szerkesztése]
[Lexikon kezdőlapra lépés]
|
