Bråkdiagram isomorfism
I grafteorin är en fraktionerad isomorfism av grafer vars närliggande matriser betecknas A och B en dubbelstokastisk matris D så att DA = BD . Om den dubbelstokastiska matrisen är en permutationsmatris , så utgör den en grafisomorfism .
Beräkningskomplexitet
Medan problemet med grafisomorfism inte är känt för att kunna avgöras i polynomtid och inte är känt för att vara NP-komplett , är problemet med fraktionell grafisomorfism avgörbart i polynomtid eftersom det är ett specialfall av det linjära programmeringsproblemet , för vilket det finns en effektiv lösning.
Motsvarighet till den grövre rättvisa uppdelningen
Två grafer är också fraktionellt isomorfa om de har en gemensam grövre rättvis partition. En partition av en graf är en samling av parvis osammanhängande uppsättningar av hörn vars förening är grafens vertexuppsättning. En partition är likvärdig om för valfritt par av hörn u och v i samma block av partitionen och vilket block B som helst på partitionen, både u och v har samma antal grannar i B . En rättvis partition P är grövre om varje block i någon annan rättvis partition är en delmängd av ett block i P . De två grövre jämlika partitionerna P och Q är vanliga om det finns en bijektion f från blocken av P till blocken av Q , så att för alla block B och C i P är antalet grannar i C av någon vertex i B lika med antalet av grannar i f(C) till valfri vertex i f(B) .
Se även
- Scheinerman, Edward; Ullman, Daniel (20 december 2013). Fractional Graph Theory . Dover Publikationer. ISBN 978-0486485935 .