Springen naar inhoud

[scheikunde] Graventheorie


  • Log in om te kunnen reageren

#1

MeA_BzZz

    MeA_BzZz


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 04 juni 2007 - 21:10

Iemand enig idee?
Zij G = (V, E) een graaf. Het complement G = (V, E complement) van G is de graaf waarin u en v verbonden zijn als en alleen als ze in G niet verbonden zijn. Let op, G en G complement hebben dus dezelfde puntenverzameling V, maar "complementaire"lijnenverzamelingen.
Bewijs dat als G onsamenhangend is dan G complement samenhangend moet zijn.
Geef een voorbeeld waaruit blijkt dat als G samenhangend is G complement niet onsamenhangend hoeft te zijn.

Defenitie 2.7 Een wandeling van vo naar vk in een graaf G is een rij vo, e1, v1, e2, v2,... , ek, vk van afwisselend punten en lijnen in G zo dat lijn ei de punten vi-1 en vi verbindt (i=1,2,..., k). Het aantal lijnen in de wandeling is de lengte ervan. De wandeling, ook te noteren met vo  v1  v2  ...  vk, heeft beginpunt vo en eindpunt vk. Als begin- en eindpunt gelijk zijn en k≥1, dan heet de wandeling gesloten, anders open.

Defenitie 2.13 Een graaf G is samenhangend als tussen elk tweetal punten van G een wandeling bestaat, anders onsamenhangend.

Ik heb een schets gemaakt van een vijpuntige ster en dan de punten van de ster aan elkaar gelinkt. Dan zijn de gelinkte punten G en de ster dan G complement.

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

#2

rwwh

    rwwh


  • >5k berichten
  • 6847 berichten
  • Moderator

Geplaatst op 04 juni 2007 - 21:27

Dit lijkt me wiskundig...

Heb je zelf al geprobeerd de bewijzen te vinden? Je vijfpuntige ster is een voorbeeld dat voldoende is voor de tweede vraag, maar het eerste bewijs heb je niet geleverd. Probeer eens te beginnen met een onsamenhangende graaf waarvan je verder helemaal niets aanneemt: simpelweg een splitsing van alle nodes in twee groepen die onderling geen verbinding hebben. Hoe ziet het complement van die graaf eruit?

Veranderd door rwwh, 04 juni 2007 - 21:31


#3

stoker

    stoker


  • >1k berichten
  • 2746 berichten
  • Ervaren gebruiker

Geplaatst op 05 juni 2007 - 07:57

van je eerste vraag
stel dat je graaf bestaat uit 1 samenhangende en 2 apparte knooppunten met 1 tak
als je dan het complement neemt, moet elk punt van je samenhangende graaf verbonden zijn met de twee punten en is je G' dus samenhangend
algemener geldt dat ook

#4

MeA_BzZz

    MeA_BzZz


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 07 juni 2007 - 13:26

ok, dit heb ik voor vraag 1:

Er zijn n lijnen mogelijk tussen een aantal van v punten, zodanig dat de graaf G samenhangend is. Als men dan n-1,n-2,n-3... lijnen heeft waardoor de graaf G onsamenhangend wordt dan krijg zijn complement G' n+1, n+2... lijnen waardoor G' samenhangen is of blijft.

Klopt, of BS?

#5

stoker

    stoker


  • >1k berichten
  • 2746 berichten
  • Ervaren gebruiker

Geplaatst op 07 juni 2007 - 13:38

ok, dit heb ik voor vraag 1:

Er zijn n lijnen mogelijk tussen een aantal van v punten, zodanig dat de graaf G samenhangend is. Als men dan n-1,n-2,n-3... lijnen heeft waardoor de graaf G onsamenhangend wordt dan krijg zijn complement G' n+1, n+2... lijnen waardoor G' samenhangen is of blijft.

Klopt, of BS?

ik snap het niet zo goed

"Als men dan n-1,n-2,n-3... lijnen heeft waardoor de graaf G onsamenhangend wordt"
bedoel je dan dat de graaf G met n-1 takken, niet samenhangend is? bij een willekeurig G dus? want dat is BS!

teken eens een simpel geval van je te bewijzen

#6

rwwh

    rwwh


  • >5k berichten
  • 6847 berichten
  • Moderator

Geplaatst op 07 juni 2007 - 20:30

Zoals ik eerder suggereerde, een onsamenhangende graaf is te splitsen in twee grafen (misschien wel op meerdere manieren). Zet alle punten van het eerste deel links, en alle punten van het tweede deel rechts. Hoe ziet het complement er nu uit?

#7

stoker

    stoker


  • >1k berichten
  • 2746 berichten
  • Ervaren gebruiker

Geplaatst op 08 juni 2007 - 12:59

Ik ben wel benieuwd geworden wie dat allemaal ziet, grafen, in Nederland.

want voor zover ik weet zijn er niet zoveel in Belgie die dat in hun lessenpaket hebben.

#8

jana_CF

    jana_CF


  • >250 berichten
  • 264 berichten
  • Ervaren gebruiker

Geplaatst op 08 juni 2007 - 14:05

nog nooit van gehoord en ik heb wiskunde wetenschappen gedaan 8-[
maar wiskunde ligt niet helemaal in mn interessesfeer :oops:

#9

stoker

    stoker


  • >1k berichten
  • 2746 berichten
  • Ervaren gebruiker

Geplaatst op 08 juni 2007 - 15:01

nog nooit van gehoord en ik heb wiskunde wetenschappen gedaan 8-[
maar wiskunde ligt niet helemaal in mn interessesfeer :oops:

juist daarom dat ik het vraag, in belgie ziet niemand dat in het middelbaar. En in het hogere zijn die richtingen waar ze dat zien ook wel op 1 (of mss twee) handen te tellen.

#10

rwwh

    rwwh


  • >5k berichten
  • 6847 berichten
  • Moderator

Geplaatst op 08 juni 2007 - 21:01

In het standaard lespakket zit het niet. Groepentheorie ook niet. Maar soms dan doe je wetenschappelijk onderzoek waarbij je het nodig hebt, en dan kun je zelf iets lezen of een wiskundige opzoeken voor hulp.

Grafentheorie kun je gebruiken voor het beschrijven van de bindingen tussen atomen, de topologie van een molecuul. Dus ook als scheikundige kun je dit soms gebruiken.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures