Blockgraf - Block graph
Inom grafteori är en gren av kombinatorisk matematik, ett blockdiagram eller ett klickträd en typ av oriktad graf där varje tvåkopplad komponent (block) är en klick .
Blockgrafer kallas ibland felaktigt för Husimi -träd (efter Kôdi Husimi ), men det namnet syftar mer korrekt på kaktusgrafer , diagram där varje icke -ansluten komponent är en cykel.
Blockgrafer kan karakteriseras som skärningslinjerna för blocken av godtyckliga oriktade grafer.
Karakterisering
Blockgrafer är exakt de grafer för vilka, för varje fyra hörn u , v , x och y , de två största av de tre avstånden d ( u , v ) + d ( x , y ), d ( u , x ) + d ( v , y ) och d ( u , y ) + d ( v , x ) är alltid lika.
De har också en förbjuden grafkarakterisering som graferna som inte har diamantdiagrammet eller en cykel med fyra eller flera hörn som en inducerad subgraf ; det vill säga de är de diamantfria ackordgraferna. De är också de Ptolemaiska graferna ( ackordavståndsärftliga grafer ) där varannan nod på avstånd två från varandra är förbundna med en unik kortaste väg , och ackordgraferna där varannan maximala klick har högst en toppunkt gemensamt.
En graf G är en blockgraf om och endast om skärningspunkten mellan varannan anslutna delmängd av hörn för G är tom eller ansluten. Därför bildar de anslutna delmängderna av hörn i ett anslutet blockdiagram en konvex geometri , en egenskap som inte stämmer för några grafer som inte är blockdiagram. På grund av den här egenskapen, i en ansluten blockgraf, har varje uppsättning hörn en unik minimal ansluten superset, dess stängning i den konvexa geometrin. De anslutna blockgraferna är exakt de grafer där det finns en unik inducerad väg som förbinder varje par hörn.
Relaterade grafklasser
Blockgrafer är ackordala , distansärftliga och geodetiska . De avståndsarvliga graferna är graferna där varannan inducerade väg mellan samma två hörn har samma längd, en försvagning av karakteriseringen av blockgrafer som har högst en inducerad väg mellan varannan hörn. Eftersom både ackordgraferna och avståndsärftliga graferna är underklasser av de perfekta graferna , är blockgrafer perfekta.
Varje träd , klusterdiagram eller väderkvarngraf är ett blockdiagram.
Varje blockgraf har högst två bokstäver .
Blockgrafer är exempel på pseudomedianska grafer : för varje tre hörn finns antingen en unik toppunkt som tillhör de kortaste banorna mellan alla tre hörnen, eller så finns det en unik triangel vars kanter ligger på dessa tre kortaste vägar.
De linjediagram av träd är exakt blockdiagram där varje skär vertex infaller till högst två block, eller ekvivalent klo fria blocket grafer. Linjediagram över träd har använts för att hitta grafer med ett visst antal kanter och hörn där den största inducerade subgrafen som är ett träd är så liten som möjligt.
Blockgraferna där varje block har högst tre storlekar är en speciell typ av kaktusgraf , en triangulär kaktus. Den största triangulära kaktusen i någon graf kan hittas under polynomtid med hjälp av en algoritm för matroidparitetsproblemet . Eftersom triangulära kaktusgrafer är plana grafer kan den största triangulära kaktusen användas som en approximation till den största plana subgrafen, ett viktigt delproblem vid planarisering . Som en approximationsalgoritm har denna metod approximationsförhållandet 4/9, det mest kända för det maximala plana subgrafproblemet.
Blockera grafer för oreglerade grafer
Om G är en oriktad graf, är blockdiagrammet för G , betecknat B ( G ), snittdiagrammet för blocken i G : B ( G ) har en toppunkt för varje dubbelkopplad komponent i G och två hörn för B ( G ) är intilliggande om motsvarande två block möts vid en ledpunkt. Om K 1 betecknar grafen med en toppunkt, definieras B ( K 1 ) som den tomma grafen . B ( G ) är nödvändigtvis ett blockdiagram: den har en bikopplad komponent för varje artikuleringstopp för G , och varje dubbelkopplad komponent som bildas på detta sätt måste vara en klick. Omvänt, är varje block diagram grafen B ( G ) för vissa graf G . Om G är ett träd, då B ( G ) sammanfaller med linjediagrammet av G .
Diagrammet B ( B ( G )) har en hörnpunkt för varje ledfördelningstopp för G ; två hörn är intill varandra i B ( B ( G )) om de hör till samma block i G .