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
- Medier relateret til Matrix-repræsentation af grafer på Wikimedia Commons