[scheikunde] Graventheorie

MeA_BzZz

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.

rwwh

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?

stoker

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

MeA_BzZz

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?

stoker

MayaPar25 schreef: 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

rwwh

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?

stoker

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.

jana_CF

nog nooit van gehoord en ik heb wiskunde wetenschappen gedaan 8-[

maar wiskunde ligt niet helemaal in mn interessesfeer

stoker

jana schreef: nog nooit van gehoord en ik heb wiskunde wetenschappen gedaan 8-[

maar wiskunde ligt niet helemaal in mn interessesfeer

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.

rwwh

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.

Wetenschapsforum

Laatste berichten

Nieuwsberichten

[scheikunde] Graventheorie

[scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie

Re: [scheikunde] Graventheorie