Pojdi na vsebino

Paleyjev graf

Iz Wikipedije, proste enciklopedije
Paleyjev graf
Paleyjev graf reda 13
ImeRaymond Paley
Točkeq ≡ 1 mod 4,
q je praštevilska potenca
Povezaveq(q − 1)/4
Značilnostikrepkoregularen
konferenčen
sebikomplementaren
Označba

Paleyjevi grafi so v teoriji grafov gosti neusmerjeni grafi skonstruirani iz članov primernega končnega obsega s povezovanjem parov elementov, ki se razlikujejo v kvadratnem ostanku. Imenujejo se po angleškem matematiku Raymondu Paleyju. Paleyjevi grafi tvorijo neskončno družino konferenčnih grafov, kar vodi do neskončne množice simetričnih konferenčnih matrik. Paleyjevi grafi omogočajo rabo orodij iz teorije grafov pri raziskovanju teorije števil kvadratnih ostankov in imajo zanimive značilnosti, tako da so v teoriji grafov uporabni splošneje.

Paleyjevi grafi so v tesni povezavi s Payleyjevo konstrukcijo za konstruiranje Hadamardovih matrik iz kvadratnih ostankov.[1] Kot grafe so jih neodvisno vpeljali Horst Sachs leta 1962 ter Paul Erdős in Alfréd Rényi leta 1963.[2][3] Sachs se je zanimal zanje zaradi njihove sebi komplementarnosti, Erdős in Rényi pa sta raziskovala njihove simetrije.

Sklici

[uredi | uredi kodo]
  1. Payley (1933).
  2. Sachs (1962).
  3. Erdős, Rényi (1963).
  • Erdős, Paul; Rényi, Alfréd (1963). »Asymmetric graphs«. Acta Mathematica Academiae Scientiarum Hungaricae. Zv. 14. str. 295–315. doi:10.1007/BF01895716. MR0156334.
  • Paley, Raymond (1933). »On orthogonal matrices«. J. Math. Phys. Zv. 12. str. 311–320.
  • Sachs, Horst (1962). »Über selbstkomplementäre Graphen«. Publicationes Mathematicae Debrecen. Zv. 9. str. 270–288. MR0151953.

Zunanje povezave

[uredi | uredi kodo]