Dot-produktrepræsentation af en graf - Dot product representation of a graph

En prikproduktrepræsentation af en simpel graf er en metode til at repræsentere en graf ved hjælp af vektorrum og prikproduktet fra lineær algebra . Hver graf har en prikproduktrepræsentation.

Definition

Lad G være en graf med toppunkt sæt V . Lad F være et felt, og f en funktion fra V til F k, således at xy er en kant af G, hvis og kun hvis f ( x ) · f ( y ) ≥  t . Dette er dot produkt repræsentation af G . Antallet t kaldes punktproduktgrænsen , og den mindste mulige værdi af k kaldes punktproduktdimensionen.

Ejendomme

  • En tærskelgraf er en prikproduktgraf med positiv t og prikproduktdimension 1.
  • Hvert intervalgraf har højst punktproduktdimension 2.
  • Hver plan graf har højst punktdimension 4.

Se også

Referencer

eksterne links