Grafuppräkning - Graph enumeration

Den fullständiga listan över alla fria träd på 2,3,4 märkta hörn: träd med 2 hörn, träd med 3 hörn och träd med 4 hörn.${\ displaystyle 2^{2-2} = 1}$${\ displaystyle 3^{3-2} = 3}$${\ displaystyle 4^{4-2} = 16}$

I kombinatorik , ett område i matematik , beskriver grafräkning en klass av kombinatoriska uppräkningsproblem där man måste räkna oriktade eller riktade grafer av vissa typer, typiskt som en funktion av antalet hörn i grafen. Dessa problem kan lösas antingen exakt (som ett algebraiskt uppräkningsproblem ) eller asymptotiskt . Pionjärerna inom detta område av matematik var George Pólya , Arthur Cayley och J. Howard Redfield .

Märkta vs omärkta problem

I vissa grafiska uppräkningsproblem anses grafens hörn vara märkta på ett sådant sätt att de kan särskiljas från varandra, medan i andra problem varje permutation av hörnen anses bilda samma graf, så hörnen anses identiska eller omärkta . I allmänhet tenderar märkta problem att vara enklare. Som med kombinatorisk uppräkning mer allmänt är Pólyas uppräkningssats ett viktigt verktyg för att reducera omärkta problem till märkta: varje omärkt klass betraktas som en symmetrisklass av märkta objekt.

Exakta uppräkningsformler

Några viktiga resultat på detta område inkluderar följande.

• Antalet märkta n -vertex enkel oriktade grafer är 2 ^{n ( n  - 1) / 2} .
• Antalet märkta n -vertex enkla riktade grafer är 2 ^{n ( n} -1  ⁾ .
• Antalet C _n av anslutna märkta n -vertex -ostyrda grafer uppfyller återkommande förhållande

${\ displaystyle C_ {n} = 2^{n \ välj 2}-{\ frac {1} {n}} \ sum _ {k = 1}^{n-1} k {n \ välj k} 2^ {nk \ välj 2} C_ {k}.}$

från vilken man enkelt kan beräkna, för n = 1, 2, 3, ..., att värdena för C _n är

1, 1, 4, 38, 728, 26704, 1866256, ... (sekvens A001187 i OEIS )

• Antalet märkta n -vertex fria träd är n ^{n  - 2} ( cayleys formel ).
• Antalet omärkta n -vertex larver är

${\ displaystyle 2^{n-4} +2^{\ lfloor (n-4)/2 \ rfloor}.}$

Grafdatabas

Olika forskargrupper har tillhandahållit sökbar databas som listar grafer med vissa egenskaper av små storlekar. Till exempel

• Grafernas hus
• Liten grafdatabas

Referenser