Kurve

Grafer er diskrete matematiske strukturer som er av interesse for både matematikk og et bredt spekter av bruksområder. På matematikkfeltet utgjør deres studie, teorien om grafer , en viktig del av kombinatorikken ; grafer brukes også i områder som topologi , automatteori , spesialfunksjoner , geometri til polyeder , Lie-algebraer . Grafer møtes i ulike kapitler innen informatikk(for eksempel for å skissere programmer, kretser, datanettverk, nettstedskart). De er også grunnlaget for systemer og prosessmodeller studert innen ingeniørvitenskap , kjemi , molekylærbiologi , operasjonell forskning , bedriftsorganisasjon , geografi (elvesystemer, veinett, transport), strukturell lingvistikk , historie (slektstrær, tekstfilologi).

Grunnleggende definisjoner

En graf er et sett med elementer kalt noder eller toppunkter som kan kobles sammen med linjer kalt buer eller sider eller kanter. Mer formelt er en graf et ordnet par sett , med et sett med noder og et sett med buer, slik at elementene til er par av elementer av ( det følger spesielt at ). Enda mer formelt er en graf en trippel , der den kalles settet med noder, kalles settet av buer og er en funksjon som assosierer hver bue i to hjørner i (i dette tilfellet vil grafen sies å være godt spesifisert ). Hvis det derimot er et multisett , kalles det en multigraf .

To hjørner forbundet med en bue kalles ender av buen; buen er også identifisert med paret som dannes av endene . Hvis det er en symmetrisk relasjon, sies grafen å være urettet (eller indirekte), ellers sies den å være orientert (eller direkte).

En bue som har to sammenfallende ender kalles en løkke . En urettet graf uten løkker kalles en enkel graf . Skjelettet til er grafen som oppnås ved å eliminere alle løkkene og erstatte hver multi-bue med en enkelt bue med de samme ytterpunktene.

Toppunktene som tilhører en bue eller kant kalles ekstremer, ekstreme punkter eller ekstreme hjørner av buen. Et toppunkt kan eksistere i en graf og ikke tilhøre en bue.

Settene og antas vanligvis å være endelige, og mange av de best kjente resultatene er ikke sanne (eller er ganske forskjellige) for uendelige grafer fordi mange av argumentene mislykkes i det uendelige tilfellet . Rekkefølgen til en graf er (antall toppunkter). Størrelsen på en graf er . Antall buer som faller inn i et toppunkt (dvs. antall buer som kobles til det) kalles toppunktgraden , der en bue som forbinder toppunktet i begge ender (en løkke) telles to ganger.

"Maksimal grad" og "minimum grad" betraktes som henholdsvis graden av toppunktet med det største antallet innfallende kanter og graden av toppunktet som har færre innfallende kanter. Når maksimumsgraden og minimumsgraden faller sammen med et tall , er vi i nærvær av en -regulær graf (eller mer enkelt vanlig graf).

For en bue bruker grafteoretikere vanligvis den mest syntetiske notasjonen .

En graf uten kanter kalles en nullgraf . Et ekstremt tilfelle av en nullgraf er det for grafen , som settet med noder også er tomt for. [1]

Full graf, tetthet av en graf

En graf er definert komplett hvis to av dens toppunkter er tilstøtende (det er en bue som forbinder dem). Den maksimale kardinaliteten til en fullstendig undergraf av grafen kalles grafens tetthet .

Stier, stier, kretser og sykluser

En "bane" med lengde n i G er gitt av en sekvens av toppunkter v 0 , v 1 , ..., v n (ikke nødvendigvis alle distinkte) og av en sekvens av kanter som forbinder dem (v 0 , v 1 ) , (v 1 , v 2 ), ..., (v n-1 , v n ) . Toppene v 0 og v n kalles ytterpunktene av banen.

En sti med to sider som er forskjellige fra hverandre kalles en sti .

En lukket bane ( v 0 = v n ) uten gjentatte buer kalles en krets .

En lukket bane ( v 0 = v n ) uten kanter eller gjentatte noder kalles en syklus .

Banen å følge for å sende pakker fra en node til en annen er en minimal bane.

Tilkobling

Gitt en graf G = (V, E) sies to toppunkter v, u ∈ V å være "sammenkoblet" hvis det finnes en bane med endepunkter v og u . Hvis en slik bane ikke finnes, sies v og u å være "frakoblet". Forbindelsesforholdet mellom toppunkter er et ekvivalensforhold .

For i = 1, ..., k ( k ekvivalensklasser ) kan undergrafene G i = (V i , E i ) defineres som de maksimale undergrafene som inneholder alle elementene som er koblet til hverandre, som tar navnet tilkoblede komponenter av G , hvis kardinalitet ofte er betegnet med γ ( G ).

Hvis γ ( G ) = 1, sies G å være " koblet ".

En "isolert node" er et toppunkt som ikke er koblet til noe annet toppunkt. En isolert node har grad 0.

En "bro" og et "kryss" er henholdsvis en bue og et toppunkt som, hvis de undertrykkes, kobler fra grafen.

"Konnektiviteten" til en graf G = (V, E) er definert som kardinaliteten til det ikke-tomme settet S ⊂ V slik at G \ S ( G hvorfra alle nodene til S er eliminert ) er frakoblet eller er en isolert knute.

Tilsvarende er "bueforbindelsen" definert som kardinaliteten til det ikke-tomme settet A ⊂ E slik at G \ A ( G hvorfra alle kantene til A er eliminert ) er frakoblet. Sløyfene er irrelevante i beregningen av bueforbindelsen, mens multibuene telles etter antall buer de inkluderer.

La være tilkoblingen til G angitt med κ ( G ), buetilkoblingen til G angitt med κ '( G ) og minimumsgraden av G angitt med δ min ( G ).

"Whiteny-teoremet" sier at for enhver graf G gjelder relasjonen κ ( G ) ≤ κ '( G ) ≤ δ min ( G ).

Kobling og overlegg

Gitt en enkel graf G = (V, E) , er en mengde M = (S, A) sammensatt av par av toppunkter tatt to og to og kantene som forbinder disse toppunktene er en kobling (eller matching eller matching) hvis hvert toppunkt av S har grad 0 eller 1.

Spesielt kalles hver node med grad 1 " m -mettet" og hver node med grad 0 kalles " m -eksponert".

Gitt en matchende M = (S, A) på G = (V, E) , er en bane P ⊆ E "m-vekslende" hvis P inneholder vekselvis kanter av E og kanter av A.

En m-alternerende bane er "m-augmenting" hvis den første og siste toppunktet på den banen er m -eksponert.

I følge "Berges teorem" er en matchende M av G maksimal hvis og bare hvis G ikke inneholder m -forsterkende baner.

Et overlegg av en graf G = (V, E) er et ikke - tomt sett S ⊆ V slik at hver bue i E faller inn i minst ett toppunkt av S. For hver graf er den maksimale kardinaliteten til et overlegg større enn eller lik kardinaliteten til maksimal matching.

La ν ( G ) være kardinaliteten til den maksimale matchingen av G og τ ( G ) den maksimale kardinaliteten til omslagene til G.

König beviste at hvis G er en todelt graf, så er ν ( G ) = τ ( G ).

I stedet, mer generelt, for enhver graf gjelder ν ( G ) ≥ τ ( G ).

Typer grafer

Grafrealisering

Det er to generelle måter å representere en graf med en datastruktur som kan brukes av et program : tilgrensningslisten og tilgrensningsmatrisen . I en tilstøtende liste inneholder en liste en liste over noder, og hver node er koblet med en liste over pekere til noder forbundet med en bue. I en tilstøtende matrise har en matrise , hvor er antall noder, en sann verdi i en celle hvis noden er koblet til noden . Matrisen er kun symmetrisk hvis grafen ikke er orientert.

Indikert med V kardinaliteten til settet med toppunkter i grafen og med E kardinaliteten til settet med buer i grafen, krever de to representasjonene, den ene gjennom lister og den gjennom tilstøtende matrisen , henholdsvis Θ (V + E ) og Θ (V 2 ) minneplass.

Hver av de to representasjonene har noen fordeler: en tilstøtende liste er mer egnet for å representere spredte grafer eller grafer med få buer, derfor er det enkelt å finne alle nodene ved siden av en gitt node og verifisere eksistensen av forbindelser mellom noder; en tilstøtende matrise er derimot mer egnet for å beskrive tette grafer med mange buer, og det gjør det også lettere å invertere grafene og identifisere undergrafene deres.

Syntaks for grafrepresentasjon

Det er flere syntakser for grafrepresentasjon, noen basert på XML -språk , for eksempel DGML , DotML , GEXF , GraphML , GXL og XGMML , og andre tekstlige, for eksempel DOT , Graph Modeling Language (GML), LCF og Trivial Graph Format .

Applikasjoner

Grafteori har mange bruksområder for modellering av telekommunikasjonsnettverk , nevrale nettverk , i biologi, i økonomiske og sosiale vitenskaper.

Fra de økonomiske og sosiale vitenskapene på 1980-tallet begynte adopsjonen av en bestemt type nettverk ( kjerne-periferi-nettverk ) å spre seg blant forskere og akademikere, dannet av en sentral blokk, mer "tett" av forbindelser mellom nodene, og av en perifer blokksett med noder med spredte lenker. Samtidig ble forskjellige partisjoneringsmetoder ( og tilkoblingsbegrensninger) foreslått, samt mål på sentraliteten til nodene for å teste modellens anvendelighet på individuelle nettverk [2] .

Denne typen nettverk ble opprettet for å modellere og forklare den ulik økonomiske veksten mellom land, det vil si tendensen til konsentrasjonen av økonomisk og finansiell rikdom observert i landsystemer fra den andre etterkrigstiden. Modellen ble deretter utvidet til andre forskningsfelt.

Det er en "tre-blokk"-variant av "senter-periferi"-nettverket: senter-semi-hyperferi-periferi.

Merknader

  1. ^ Noen definerer grafen G = (V, ∅) tom , med V ≠ ∅, og grafen G = (∅, ∅) null .
  2. ^ Fabio Della Rossa , Fabio Dercole & Carlo Piccardi, Profiling core-periphery network structure by random walkers , på nature.com , 19. mars 2013. Hentet 4. april 2018 .

Relaterte elementer

Andre prosjekter

Eksterne lenker