Springen naar inhoud

[wiskunde] grafen


  • Log in om te kunnen reageren

#1

adesitter

    adesitter


  • 0 - 25 berichten
  • 18 berichten
  • Gebruiker

Geplaatst op 07 mei 2009 - 22:20

Kan iemand me helpen met deze opgaven?

Definitions necessary for the exercise:
(1) A graph G is called a connected Graph if every pair of distinct vertices v in the graph can be reached through some path.
(2) A graph G is a planar graph if it can be drawn in the plane in such a way that its edges intersect only at their endpoints. The faces of such a graph are regions bounded by the edges (the outer region of the graph is a face as well!)

Exercise:

G is an undirected, connected, planar graph and c is the length of the shortest cycle in G. Show that

m ≤ c(n-2) / (c-2)
where m is the number of edges and n is the number of vertices in the graph.

Hint:

The number of edges m, the number of vertices n and the number of faces f in a planar graph are related via Euler's formula:

n - m + f = 2

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

TD

    TD


  • >5k berichten
  • 24052 berichten
  • VIP

Geplaatst op 07 mei 2009 - 23:40

Welkom op het forum Huiswerk en Practica.

Jij wilt vlot hulp. Dat is alleen goed mogelijk als je daar zelf wat voor doet.

Naast de algemene regels van dit forum hebben we voor dit huiswerkforum een paar speciale regels en tips.
Die vind je in de huiswerkbijsluiter

In die huiswerkbijsluiter staat bijvoorbeeld:

Quote

VAKGEBIED-TAGS
Plaats het vakgebied waarop je vraag betrekking heeft tussen rechte haken in de titel.
bijv: [biologie] of [frans]. Zo blijft dit huiswerkforum overzichtelijk.

Hebben we even voor je gedaan. Denk je er de volgende keer zelf aan?
"Malgré moi, l'infini me tourmente." (Alfred de Musset)

#3

adesitter

    adesitter


  • 0 - 25 berichten
  • 18 berichten
  • Gebruiker

Geplaatst op 08 mei 2009 - 14:05

Sorry, maar het vak waar ik deze vraag bij heb gekregen is bioinformatica dus ik heb daar bij geplaatst.
Ik zal volgende keer proberen wat verder te zoeken.

Verder loop ik echt vast met deze vraag, ik weet dat ik moet kijken naar undirecte en directe en dat daar de link ligt alleen ik kom er echt niet uit.

Iemand hulp?





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures