Grafer och nätverkIntroduktion

Varje dag omges vi av otaliga anslutningar och nätverk: vägar och järnvägsspår, telefonlinjer, internet, elektroniska kretsar och till och med molekylära bindningar. Det finns till och med sociala nätverk mellan vänner och familjer. Kan du tänka på några andra exempel?

Väg- och järnvägsnät

Datorchip

Försörjningskedjor

vänskap

Neurala anslutningar

Internet

I matematik kan alla dessa exempel representeras som diagram (inte förväxlas med grafen för en funktion). En graf består av vissa punkter som kallas , av vilka några är förbundna med .

Grafteori är studiet av grafer och deras egenskaper. Det är ett av de mest spännande och visuella områdena i matematik och har otaliga viktiga tillämpningar.

Vi kan rita layouten för enkla grafer med cirklar och linjer. Hörnpunkternas placering och kanternas längd är irrelevant - vi bryr oss bara om hur de är anslutna till varandra. Kanterna kan till och med korsa varandra och behöver inte vara raka.

I vissa grafer går kanterna bara en väg. Dessa kallas riktade diagram .

Vissa grafer består av flera grupper av toppar som inte är förbundna med varandra genom kanter. Dessa diagram är frånkopplade .

Andra grafer kan innehålla flera kanter mellan samma par av hörn, eller hörn som är anslutna till sig själva (slingor).

Vi kan skapa nya grafer från en befintlig graf genom att ta bort en del av hörn och kanter. Resultatet kallas en subgraf . Här kan du se några fler exempel på grafer, med färgade kanter och hörn som indikerar en möjlig undergraf:

Vi säger att ordningen på en graf är antalet vertikaler som den har. Graden av ett toppunkt är antalet kanter som möts vid det toppunktet.

Beställning:

Examen:

Grafer som består av en enda ögla med vertikaler kallas cykler . Alla cykler har .

Utrustad med dessa nya definitioner, låt oss utforska några av de fascinerande egenskaperna och tillämpningarna av grafer.

Ändra språk

Logga in på Mathigon

Dela med sig

Återställ framsteg

Ordlista

Grafer och nätverkIntroduktion