Modulär graf - Modular graph
I grafteori , en gren av matematiken, de modulära grafer är oriktade grafer i vilka var tredje hörn x , y och z har minst en median vertex m ( x , y , z ) som tillhör kortaste vägar mellan varje par av x , y och z . Deras namn kommer från det faktum att ett ändligt gitter är ett modulärt galler om och bara om dess Hasse -diagram är ett modulärt diagram.
Det är inte möjligt för en modulär graf att innehålla en cykel med udda längder. Om C är en kortaste udda cykel i en graf, är x en hörnpunkt för C och yz är kanten på C längst från x , det kan inte finnas någon median m ( x , y , z ) för de enda hörnen på den kortaste vägen yz är y och z själva, men ingen av dem kan tillhöra en kortaste väg från x till den andra utan att genväga C och skapa en kortare udda cykel. Därför är varje modulgraf en tvåpartig graf .
De modulära graferna innehåller som ett specialfall mediangraferna , där varje trippel av hörn har en unik median; mediangrafer är relaterade till distributiva galler på samma sätt som modulgrafer är relaterade till modulära galler. De modulära graferna innehåller emellertid också andra grafer, till exempel de fullständiga bipartitgraferna där medianerna inte är unika: när de tre hörnen x , y och z alla tillhör ena sidan av bipartitionen av ett komplett bipartitdiagram, varje hörnpunkt på andra sidan är en median. Varje ackordbipartitgraf (en klass av grafer som innehåller de fullständiga bipartitgraferna och de bipartitavståndsärftliga graferna ) är modulär.