Springen naar inhoud

Grafen


  • Log in om te kunnen reageren

#1

bruttertje

    bruttertje


  • 0 - 25 berichten
  • 12 berichten
  • Gebruiker

Geplaatst op 06 juni 2011 - 10:53

Beste Wiskundigen,

Ik heb 2 vragen waarvan ik niet zie hoe ik ze moet oplossen, misschien kunnen jullie mij helpen?

Geplaatste afbeelding



Alvast bedankt,
Bruttertje

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

#2

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 06 juni 2011 - 11:12

Bij vraag 1. Stel eventjes dat H gewoon ťťn punt uit je graaf is, noem het v. Kun je dan de driehoeksongelijkheid bewijzen? Het bewijs komt in se gewoon neer op opschrijven wat d(u,v) juist betekent.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#3

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 06 juni 2011 - 11:12

Probeer bij vraag 1 de vergelijking eens uit te drukken in tekst (bijvoorbeeld d(u,H) = de afstand van punt u tot de deelgraaf H).

#4

bruttertje

    bruttertje


  • 0 - 25 berichten
  • 12 berichten
  • Gebruiker

Geplaatst op 07 juni 2011 - 16:36

vraag 2 snap ik volgens mij wel:
als t goed is, is het niet mogelijk om een gesloten wandeling te maken zonder cykels en zonder een lijn die 2 keer doorlopen wordt want als de lijn niet 2x wordt doorlopen dan ga je naar het volgend punt en niet terug en vervolgens naar het eindpunt maar dan zou dat een cykel zijn.

om dit bewijs mooi op te schrijven zou je dan niet de defenitie van een cykel gebruiken?
Je neemt dus aan dat er geen lijn is die 2 keer achter elkaar doorlopen wordt dus alle lijnen zijn verschillend?
Dus met andere woorden neem je aan dat er in de gesloten wandeling R geen lijn is die 2x achter elkaar wordt doorlopen, en dit zou dan per defenitie een cykel moeten zijn aangezien de defenitie van een cykel in mijn boek is gedefinierd als: Een cykel is een gesloten wandeling waarin alle lijnen en alle punten ( afgezien van begin-en eindpunt) verschillend zijn.

Bij vraag 1:
Ga ik van 2 situaties uit:
1) W ligt op het kortste pad van u naar H
2) W ligt niet op het kortste pad van u naar H

Voor situatie 1 snap ik het wel.
w ligt dan op de weg van u naar H
dus: d(u,w) + d(w,H) is precies gelijk aan de afstand (u,H) als ik het goed heb?

Bij situatie 2 snap ik 't niet echt.
als ik het voor mezelf teken wordt het wel een beetje duidelijker,
maar als w niet op het kortste pad ligt dan geldt eigenlijk gelijk:
d(u,H) kleiner d(w,H)
omdat w "achter" u ligt?


ik hoop dat jullie het nog een beetje begrijpen wat ik bedoel

#5

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 07 juni 2011 - 17:42

Bij vraag 1 maak je het jezelf in mijn ogen onnodig moeilijker... Wŗt betekent die d(.)-functie in woorden? Eens je daar deftig uit bent, moet dat onderscheid niet meer.
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#6

bruttertje

    bruttertje


  • 0 - 25 berichten
  • 12 berichten
  • Gebruiker

Geplaatst op 07 juni 2011 - 18:47

d(u,H) betekend de afstand van u naar H

#7

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 07 juni 2011 - 18:50

Maar is dit een willekeurige afstand? Hoe bepaal je die afstand?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#8

bruttertje

    bruttertje


  • 0 - 25 berichten
  • 12 berichten
  • Gebruiker

Geplaatst op 07 juni 2011 - 18:52

d(u,H) is de lengte van een korste pad tussen u en H

#9

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 07 juni 2011 - 18:54

Idd... Dus als je nu ergens een tussenstop maakt. Of dat punt nu op je pad ligt, of niet, dan is die afstand toch groter?

(Voor de goede orde, je "bewijs" klopte dus hŤ, maar een onderscheid is niet nodig simpelweg)
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#10

bruttertje

    bruttertje


  • 0 - 25 berichten
  • 12 berichten
  • Gebruiker

Geplaatst op 07 juni 2011 - 18:55

ja dat begrijp ik,
alleen probeer ik een manier te vinden om dit met behulp van een waterdicht bewijs aan te tonen.

#11

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 07 juni 2011 - 19:44

Een bewijs moet niet steeds moeilijker zijn hoor... In se heb je nu een bewijs. Maar indien dit niet bevredigend is. Je kunt eens kijken naar een bewijs uit het ongerijmde. Stel dus dat d(u, H) > d(u, w) + d(w, H). Waarom kan dat niet?

Veranderd door Drieske, 07 juni 2011 - 19:44

Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#12

bruttertje

    bruttertje


  • 0 - 25 berichten
  • 12 berichten
  • Gebruiker

Geplaatst op 07 juni 2011 - 19:52

als w op een kortste pad ligt tussen u en H
dan geldt d(u,w) + d(w,H) = d(u,H)
Dus zou je stelling niet kloppen
Maar dan mag je er toch niet gelijk van uitgaan dan het een kleiner gelijk teken moet zijn of wel?

#13

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 07 juni 2011 - 19:54

Heb je naar die link gekeken? Een bewijs uit het ongerijmde is dat je stelt dat de formule die je wilt bewijzen, niet klopt. Dus hier: er bestaat minstens ťťn w zodat d(u, H) > d(u, w) + d(w, H). En dan ga je een tegenspraak afleiden. Indien die tegenspraak er is, betekent dat dat er geen zo'n w bestaat zodat d(u, H) > d(u, w) + d(w, H). En dus geldt steeds
d(u, H) <= d(u, w) + d(w, H).

Los daarvan vind ik je argumentatie niet goed. Je hebt een definitie voor d(.). Gebruik die dan ook in de tegenspraak.

Dus stel dat er een w bestaat met d(u, H) > d(u, w) + d(w, H). dan zegt de definitie je... Maak er nu iets moois van.

Veranderd door Drieske, 07 juni 2011 - 19:56

Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.

#14

bruttertje

    bruttertje


  • 0 - 25 berichten
  • 12 berichten
  • Gebruiker

Geplaatst op 07 juni 2011 - 19:58

Oke, nou bedankt voor het oplossen van de vraag!

Ik heb nog een vraag gevonden waar ik niet uitkomen,
Zou je me misschien hiermee kunnen helpen:

Vraag 3:
Bewijs dat als een graaf waarin elk punt,een graad van tenminste k heeft, er dan een pad bestaan van ten minste lengte k?

#15

Drieske

    Drieske


  • >5k berichten
  • 10217 berichten
  • Moderator

Geplaatst op 07 juni 2011 - 20:11

Kun je het hele bewijs dan eens geven evt?

En bij die 3: wat heb je zelf al geprobeerd?
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures