Matte problem, universitetsnivå

2012-04-28, 11:05

#1

Medlem

Reg: May 2008

Inlägg: 2 642

Citat:

Let G = (V, E) be a connected planar graph with v vertices and e edges, in which each cycle has a length of at least c.

Use Euler's theorem and the fact that the degree of each face is the length of the cycle enclosing it to prove that:

e≤c(v-2)/(c-2)

Tack på förhand

Citera

2012-04-28, 11:53

#2

Medlem

Reg: Sep 2005

Inlägg: 539

Enligt Euler's sats har vi att
v - e + f = 2

Genom att använda "the degree of each face is the length of the cycle enclosing it" samt definitionen av G kan vi ställa upp olikheten:
f*c >= 2*e och således f => 2e/c
Substituera i Euler's sats så får vi att
v - e + 2e/c >= 2 och efter lite fippel:
e ≤ c(v-2)/(c-2). QED

Citera

2012-04-28, 12:13

#3

Medlem

Reg: May 2008

Inlägg: 2 642

Nu när du säger det ser det så självklart ut, tusen tack

Citera

Matte problem, universitetsnivå

Stöd Flashback