Paleyjev graf

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje
Paleyjev graf
Paley13.svg
Paleyjev graf reda 13
Ime Raymond Paley
Točke q ≡ 1 mod 4,
q je praštevilska potenca
Povezave q(q − 1)/4
Značilnosti krepko regularen
konferenčen
sebi komplementaren
Označba QR(q)\!\,

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 Raymondui 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.

Opombe[uredi | uredi kodo]

  1. ^ Payley (1933).
  2. ^ Sachs (1962).
  3. ^ Erdős, Rényi (1963).

Viri[uredi | uredi kodo]

  • Paley, Raymond (1933). "On orthogonal matrices". J. Math. Phys. 12: 311–320. 
  • Sachs, Horst (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen 9: 270–288. MR0151953. 

Zunanje povezave[uredi | uredi kodo]