Charlie brugte matematik til at finde ud af, hvor folk sad i baren, før de allesammen blev skudt. Jeg hørte det som aggregerede modeller. Amita nævnte en anvendelse af grafteori for at matche nyrepatienter med donorer. Charlie havde udregnet decimaler i Euler-Mascheroni-konstanten, og han snakkede om Goldbach-formodningen. Til sidst brugte de “Hidden Markov Models” til at analysere skjulte mønstre på DVD’en
Jeg tilstår, at jeg denne gang skriver om den matematik, der blev nævnt i forbifarten, for jeg ved simpelthen ikke, hvordan det med siddepladserne hænger sammen med noget. Hidden Markov Models har jeg skrevet om før på bloggen – jeg kaldte dem skjulte Markov processer.
Grafteori og nyrepatienter
Når en pårørende tilbyder at give sin ene nyre til en syg bror, søster, datter, søn,… sker det desværre ofte, at de ikke matcher hinanden. Hvis der er tale om venner, er det sikkert endnu mere sandsynligt.
Og donoren vil nok ikke ofre en nyre til hvem som helst.
Men hvis der nu er to donor og patient par (A,a) og (B,b), hvor A vil donere til a, B vil donere til b. Ingen af dem matcher, men A og b matcher og B og a matcher. Så giver A og B implicit en nyre til deres familiemedlemmer, eller i hvert fald giver de hver en nyre, og a og b får hver en nyre. Mere generelt skal der måske flere (donor, patient) par til at få det til at gå op.
Opgaven er nu at finde den slags mere parringer. Ofte med bibetingelser om, at nyrer ikke skal transporteres for langt, at meget syge patienter går forud, at visse match er bedre end andre. Og det hører hjemme i branchen grafteori.
En matematiker ved US Naval Academy, Sommer Gentry, har set på dette problem, og det bruges tilsyneladende på bl.a. Johns Hopkins universitetshospital. De ser, så vidt jeg kan se, kun på den simple version, hvor et par matcher et andet par. Der er en gennemgang her.
Det gælder om at optimere. En patient med blodtype 0 kan kun bruge en donor med blodtype 0, mens en donor med blodtype 0 kan bruges til mange patienter (der står, at det er alle, men så simpelt er det nu nok ikke). Så man skal helst ikke “spilde” en god donor på en “nemt parret” patient.
Her er et eksempel:
Alle knuderne (cirklerne) er donor-patient par, og kanterne er match. Hvis man nu starter med at matche par nummer 4 og nummer 17, har man dummet sig, for bagefter er det kun
meget få match tilbage.
Man ønsker altså at finde den bedste parring/matching. En parring er et udvalg af kanter, som ikke har nogen fælles knuder (man kan ikke genbruge donorer/patienter). Og man vil have så mange kanter (og dermed knuder) med som muligt.
Lidt simplere eksempler:
(Fra Wikipedia under Creative Commons – se her.)
De øverste tre er maksimale parringer – man kan ikke tilføje nogen kanter- men de er ikke optimale, for man kan sætte flere kanter ind, hvis man begynder bedre. (Bortset fra den sidste). Wikipedia kalder de optimale parringer for maximum parringer.
I b) er der en perfekt parring, idet alle knuder er med i en rød kant. Så man kan spørge: Findes der en perfekt parring? Hvilke klasser af grafer har perfekt parring? Og mere praktisk: Hvordan finder man en maksimum parring? Det sidste er besvaret. Edmonds algoritmen finder en maksimum parring i polynomiel tid. Den kaldes også stier, træer og blomster algoritmen (siger Wikipedia).
Man bygger en parring lidt ad gangen. Tilføj kanter, som ikke deler et hjørne, indtil der ikke kan tilføjes flere – man har en maksimal parring. Hvis alle hjørner er med, er den maksimum og vi er færdige. Hvis et hjørne ikke er med, kan den ikke blive bedre. Hvis mere end to hjørner ikke er med er der to muligheder:
1)Der er en udvidende sti, som er en sti, hvis kanter skiftevis er fra matchingen og ikke er det, og om starter og slutter i en knude, som ikke er parret endnu (en uparret knude).- se figuren, hvor de sorte kanter er i parringen, de lyseblå er kanter i grafen, men ikke med i matchingen.
(Fra Wikipedia-public domain)
Man laver en ny parring, hvor de kanter, der er i den udvidende sti og er sorte (er i parringen) bliver lyseblå (fjernes fra parringen). Og de kanter, der var lyseblå bliver sorte (tilføjes til parringen). Nu har vi en kant mere end før i parringen og dermed to knuder mere med.
2) Hvis der ikke er en udvidende sti, kan man ikke lave en større parring end den, man har. (Det kræver et bevis).
Algoritmen skal altså finde udvidende stier. Udvidende stier findes ved at “opdyrke en skov”. Start med alle uparrede hjørner. De er rod i hver sit træ. Tilføj alle kanter fra disse hjørner, (de er ikke i parringen, for hjørnerne var uparrede), nu er træerne 1 kant høje (eller 0, hvis der ingen kanter var). Hvis en af de nye kanter ender i et parret hjørne, tilføjes den tilhørende kant fra parringen (det gør man for alle de nye kanter.) Træerne er nu 0, 1 eller 2 kanter høje. Og man bliver ved. Hvis der opstår forbindelser på tværs mellem træer er der mulighed for, at der er en udvidet sti: Løb fra roden op i det ene træ og ned i det andet til den anden rod. Det er mere indviklet, og mere smart fundet på – man skal “trække blomster sammen”. Læs mere på Wikipedia.
Her er en skov (der vender på hovedet – det er en uvane blandt grafteoretikere og dataloger). Der er en udvidet sti fra knuden til venstre via den skrå stiplede lyseblå til knuden til højre. Hvis man skifter lyseblå kanter om til sorte og omvendt langs denne sti, har det konsekvenser for andre kanter i parringen, så man skal lave sin algoritme smart nok
fra Wikipedia – ingen betingelser for brug.
Euler Mascheroni konstanten
Euler-Mascheroni-konstanten eller bare Euler konstanten er defineret som en grænseværdi.
Lad x_n= (1+1/2+1/3+1/4+…+1/n)-ln(n)
Euler- konstanten er det tal, som x_n nærmer sig, når n bliver større og større. Man skal overveje, at der er en sådan grænseværdi. Men når man har vist det, er dette en fin definition af et tal.
Vi ved ikke, om Eulerkonstanten er rational (altså kan skrives som en brøk p/q, hvor p og q er heler tal). Vi ved heller ikke, om den er transcendent (om den er rod i et heltalspolynomium, altså løsning til en ligning a_n x^n+a_(n-1) x^(n-1)+…+a_1x -a_0=0, hvor alle a_k er hele tal).
Eksempelvis er kvadratroden af 2 irrational, men ikke transcendent, da det er rod i x^2-1.
Men pi er irrational og også transcendent, og det er grundtallet for den naturlige logaritme , e, også.
Hvis Eulertallet er rationelt, altså skrives p/q. Så ved man, at q må have mere end 242000 cifre.
Man kender de første 2 milliarder cifre i Eulerkonstanten (!!).
den optræder i mange sammenhænge – integraler, i forbindelse med Riemanns zeta funktion og mange andre steder. Se for eksempel Math World.
Leonhard Euler, som man kan se på billedet, (Public domain, da copyright på det oprindelig maleri er udløbet. Se Wikipedia) var en utroligt produktiv matematiker – en af de største, vi har haft. Lorenzo Mascheroni havde jeg ikke hørt om før, men han var italiener og har bl.a. bevist en sætning, som også danskeren Georg Mohr viste (og Mohr var først) – Mohr kendes måske af læserne fra Georg Mohr konkurrencen for gymnasieelever.
