Grafuppräkning

Grafuppräkning är en kategori av enumerativa kombinatoriska  problem där det är nödvändigt att räkna upp oriktade eller riktade grafer av vissa typer, vanligtvis som en funktion av antalet grafhörn [1] . Dessa problem kan lösas antingen exakt (som problemet med algebraisk uppräkning) eller asymptotiskt . Pionjärerna inom detta område av matematik var Poya [2] , Cayley [3] och Redfield[4] .

Markerade och omarkerade uppgifter

I vissa grafuppräkningsproblem anses grafernas hörn vara märkta , vilket gör att de kan skiljas från varandra. I andra problem anses varje permutation av hörn vara samma graf, så att hörnen anses vara identiska eller omärkta . I allmänhet tenderar märkta problem att vara enklare [1] . Redfield–Polyi-satsen är ett viktigt verktyg för att reducera ett omärkt problem till ett märkt - varje omärkt klass anses vara en symmetriklass av märkta objekt.

Exakta uppräkningsformler

Några viktiga resultat på detta område.

• Antalet märkta enkla oriktade grafer med n hörn är 2 n ( n  − 1)/2 [5]
• Antalet märkta enkla riktade grafer med n hörn är 2 n ( n  − 1) [6]
• Antalet C n av anslutna märkta oriktade grafer med n hörn uppfyller det rekursiva sambandet [7]

• Antalet märkta fria träd med n hörn är n n  − 2 ( Cayleys formel ).
• Antalet omärkta larver med n hörn är [9]

Se även

• Algebraisk grafteori
• Spektralgrafteori
• Topologisk grafteori

Anteckningar

1. ↑ 12 Harary , Palmer, 1973 .
2. ↑ Polen, 1937 , sid. 145-254.
3. ↑ Arthur Cayley  (ej tillgänglig länk) A Cambridge Alumni Database . Universitetet i Cambridge.
4. ↑ Redfield, 1927 , sid. 433-455.
5. ↑ Harary, Palmer, 1973 , sid. 3.
6. ↑ Harary, Palmer, 1973 , sid. 5.
7. ↑ Harary, Palmer, 1973 , sid. 7.
8. ↑ OEIS - sekvens A001187 _
9. ↑ Harary, Schwenk, 1973 , sid. 359–365.

Litteratur

• Harary F. , Palmer E.M. Graphical Enumeration. - Academic Press , 1973. - ISBN 0-12-324245-2 .
• Harari F., Palmer E. Uppräkning av grafer = rysk översättning av föregående stycke. - Världen , 1977.
• Harary F. , Schwenk AJ Antalet larver // Diskret matematik. - 1973. - T. 6 , nr. 4 . — S. 359–365 . - doi : 10.1016/0012-365x(73)90067-8 .
• Pólya G. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und Chemical Verbindungen  // Acta Mathematica . - 1937. - Vol. 68. - doi : 10.1007/BF02546665 .  (inte tillgänglig länk)
• Theory of group-reduced distributions // American J. Math. - 1927. - T. 49 .