Clique graf

I grafteori, en klike graf af en ikke-orienteret graf G er en anden graf K, der repræsenterer strukturen af ​​kliker i G.

Clique grafer blev drøftet i det mindste så tidligt som 1968 og en karakterisering af klike grafer blev givet i 1971.

Formel definition

En klike af en graf G er et sæt X i knudepunkter af G med den egenskab, at hvert par distinkte knuder i X støder i G. En maksimal klike af en graf G er en klike X i knudepunkter af G, således at der er nr klike Y af knudepunkter af G som indeholder alle X og mindst et andet toppunkt.

Givet en graf G, dens klike graf K er en graf, således at

  • hvert toppunkt K betegner en maksimal klike af G; og
  • to knudepunkter af K støder op, når de underliggende kliker i G-aktie mindst en vinkelspids til fælles.

Den klike graf K kan også karakteriseres som skæringspunktet grafen for de maksimale kliker af G.

Karakterisering

En graf H er den klike graf K i anden graf, hvis og kun hvis der findes en samling C kliker i H, hvis forening dækker alle kanter af H, således at C danner en Helly familie. Det betyder, at hvis S er en delmængde af C med den egenskab, at hver to medlemmer af S har en ikke-tom kryds, så S selv bør også have en ikke-tom vejkryds. Men de kliker i C ikke nødvendigvis at være maksimale kliker.

Når H = K, kan en familie C af denne type konstrueres, hvori hver klike i C svarer til et toppunkt V i G, og består af kliker i G, der indeholder v. Disse kliker har alle v i deres skæringspunkt, så de danne en klike i H. Familien C konstrueret på denne måde har Helly ejendom, fordi enhver underfamilie af C med parvise nonempty kryds skal svare til en klike i G, som kan udvides til en maksimal klike, der hører til skæringspunktet mellem den underfamilie.

Omvendt, når H har en Helly familie C af sine kliker, der dækker alle kanter H, så er det den klike graf K for en graf G hvis knudepunkter er disjunkte forening af knudepunkter af H og elementerne i C. Denne graf G har en kant for hvert par kliker i C med nonempty kryds, og for hvert par af et toppunkt af H og en klike i C, der indeholder det. Det gør dog ikke indeholder nogen kanter forbinder par af knuder i H. Den maksimale kliker i denne graf G hver består af en top af H sammen med alle de kliker i C, der indeholder det, og deres skæringspunkt graf er isomorf til H.

Men denne karakteristik ikke føre til effektive algoritmer: problemet med at genkende, om en given kurve er en klike graf er NP-komplet.

  0   0
Forrige artikel Kroatisk brasilianske
Næste artikel Antonio de la Rúa

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha