I grafteori kaldes en graf akkord , hvis hver af dens cyklusser , som har fire eller flere kanter, har en akkord (en kant, der forbinder to hjørner af cyklussen, men ikke er en del af den).
En tilsvarende definition er, hvis en cyklus uden akkorder højst har tre kanter. Med andre ord er en akkordgraf en graf uden genererede cyklusser med en længde på mere end tre.
Kordegrafer er en undergruppe af perfekte grafer . De kaldes også nogle gange cyklisk stive grafer [1] eller triangulerede grafer . (Sidstnævnte term bruges nogle gange fejlagtigt til plan triangulering. Se maksimale plane grafer .) [2]
En perfekt udelukkelsesrækkefølge i en graf er rækkefølgen af grafens hjørner, således at for hvert toppunkt v , v og naboerne til v , der er efter v i rækkefølgen, danner en klike . En graf er akkord, hvis og kun hvis den har en perfekt ekskluderingsrækkefølge [3]
Rose, Lucker og Tarjan (1976) [4] (se også Habib, McConnell, Paul, Vienneno (2000) [5] ) viste, at den perfekte elimineringsrækkefølge for en akkordgraf effektivt kan findes ved hjælp af en algoritme kendt som leksikografisk bredde- første søgning . Denne algoritme opdeler grafens toppunkter i en række sæt. Til at begynde med består sekvensen af et enkelt sæt, der indeholder alle hjørner. Algoritmen i løkken udvælger toppunktet v fra det ældste sæt i sekvensen, der indeholder de endnu ikke valgt toppunkter, og deler hvert sæt S af sekvensen i to mindre - den ene består af naboerne til toppunktet v i S , den anden omfatter alle de resterende hjørner. Når divisionsprocessen udføres for alle knudepunkter, indeholder alle sæt af sekvensen et knudepunkt hver og danner en sekvens omvendt til den perfekte elimineringsrækkefølge.
Da både den leksikografiske bredde-først søgning og kontrol af, om en ordre er perfekt undtagelse, kan udføres i lineær tid, er det muligt at genkende en akkordgraf i lineær tid. Sandwichproblemet på en akkordgraf er NP-komplet [6] , mens testgrafproblemet på en akkordgraf har polynomisk-tidskompleksitet [7] .
Sættet af alle perfekte udelukkelsesordrer af en akkordgraf kan betragtes som basisordene for en antimatroid . Chandran et al . [8] brugte denne forbindelse til antimatroider som en del af en algoritme til effektivt at opregne alle perfekte udelukkelsesordrer for en given akkordgraf.
En anden applikation til perfekt elimineringsrækkefølge er at finde den maksimale klik for en akkordgraf i polynomiel tid, mens for generelle grafer er det samme problem NP-komplet (en akkordgraf kan kun have lineært mange største kliker , mens ikke-akkordale grafer kan have eksponentielt mange af dem). For at få en liste over alle de største kliker i en akkordgraf er det nok at finde den perfekte elimineringsrækkefølge, konstruere en klike for hvert knudepunkt v fra alle tilstødende knudepunkter i rækkefølge efter v , og kontrollere, om den resulterende klik er største.
Den største klike, der har den maksimale størrelse, er den maksimale klike, og da akkordgrafer er perfekte, er størrelsen af denne klike lig med det kromatiske tal på akkordgrafen. Akkordgrafer er velordnede - den optimale farve kan opnås ved at bruge den grådige farvealgoritme , der tager hjørnerne i omvendt rækkefølge til perfekt eliminering. [9]
I enhver graf er en toppunktseparator et sæt af hjørner, hvis fjernelse gør den resterende graf afbrudt. En separator er minimal, hvis den ikke indeholder en delmængde, der også er en separator. Ifølge Dirac's sætning [1] er akkordgrafer grafer, hvor hver minimal separator er en klike. Dirac brugte denne egenskab til at bevise, at akkordgrafer er perfekte .
En familie af akkordgrafer kan defineres som det sæt af grafer, hvis toppunkter kan opdeles i tre ikke-tomme delmængder A , S , og B , således at A ∪ S og S ∪ B begge danner akkordgenererede undergrafer , S er en klike, og der er ingen kanter, der forbinder A og B. _ Dette er således grafer, der tillader rekursiv opdeling i mindre undergrafer ved hjælp af kliker. Af denne grund kaldes akkordgrafer nogle gange dekomponerbare grafer . [ti]
Et andet kendetegn ved akkordgrafer [11] bruger træer og deres undertræer.
Ud fra et sæt af undertræer af et træ kan man bestemme en undertræ -graf - en skæringsgraf , hvis toppunkt svarer til et undertræ, og en kant forbinder to undertræer, hvis de har en eller flere fælles kanter. Gavril viste, at undertræsgrafer er præcis akkordgrafer.
Repræsentation af akkordgrafer som en undertræsskæringsgraf danner en nedbrydning af grafen til træer med en træbredde , der er en mindre end størrelsen af grafens største klike. Dekomponeringen af enhver graf G til træer kan betragtes som en repræsentation af grafen G som en undergraf til akkordgrafen. At dekomponere en graf i træer er også et unionstræ i tillidsudbredelsesalgoritmen .
Intervalgrafer er undertræsskæringsgrafer , et særligt tilfælde af træer. Intervalgrafer er således en underfamilie af akkordgrafer.
Split grafer er både akkorder i sig selv og er komplementer til akkord grafer. Bender, Richmond og Wormald (1985) [12] viste, at da n har en tendens til det uendelige, tenderer brøkdelen af akkordgrafer med n toppunkter, der er opdelt, til én.
Ptolemæus-grafer er grafer, der både er akkord- og afstandsnedarvede . Kvasi-tærskelgrafer er en underklasse af ptolemæiske grafer, der er både akkordale og kografiske . Blokgrafer er en anden underklasse af ptolemæiske grafer, hvor to af de største kliker højst har et fælles toppunkt. Et særligt tilfælde er møller , som har samme toppunkt for ethvert par kliker.
Strengt akkordgrafer er grafer, der er akkordale og ikke indeholder en n-sol ( n ≥ 3) som genererede undergrafer.
K-træer er akkordgrafer, hvis største kliker og største klikseparatorer alle har samme størrelse. [13] Apollonius-grafer er kordale maksimale plane grafer , eller tilsvarende plane 3-træer. [13] Maksimale ydreplanære grafer er en underklasse af 2-træer og derfor også akkordale.
Chordal grafer er en underklasse af velkendte perfekte grafer . Andre superklasser af akkordgrafer inkluderer svage akkordgrafer, grafer uden ulige huller og grafer uden lige huller . Faktisk er akkordgrafer præcis grafer, både uden lige huller og uden ulige huller (se hul i grafteori).
Enhver kordalgraf er kontraheret , dvs. en graf, hvor enhver perifer cyklus er en trekant, eftersom perifere cyklusser er et specialtilfælde af en genereret cyklus. Kontrakterede grafer kan dannes af klikesummer af akkordgrafer og maksimale akkordgrafer. Således kontraherede grafer inkluderer maksimale plane grafer . [fjorten]