Fenda grafeo

La artikolo estas parto de serio pri grafeoteorio.

Plej gravaj terminoj grafeo arbo subgrafeo ciklo kliko grado de vertico grado de grafeo Elektitaj klasoj de grafeoj plena grafeo plena dukolora grafeo kohera grafeo arbo grafeo dudividebla Fenda grafeo regula grafeo grafeo de Euler grafeo de Hamilton grafeo senrelifa pli... Grafeaj algoritmoj A* Bellman-Ford Dijkstry Fleury Floyd-Warshall Johnson Kruskal Prim traserĉado de grafeo – en larĝeco – en profundo plej proksima najbaro Problemoj prezentataj kiel grafeaj problemo de vojaĝisto problemo de ĉina leteristo problemo de marŝrutigado problemo de kunigado de geedzoj Aliaj kodo de Gray diagramo de Hasse kodo de Prüfer Reprezentado de grafeo Glosaro de grafeoteorio

vidi • diskuti • redakti

En grafeoteorio, fenda grafeo estas grafeo en kiu la verticoj povas esti disdividitaj en klikon kaj sendependan aron.

La dispartigo en klikon kaj sendependan aron ne nepre estas unika; ekzemple, la vojo a-b-c estas fenda grafeo, verticoj de kiu povas esti disdividitaj en tri malsamaj manieroj:

• kliko {a, b} kaj la sendependa aro {c}
• kliko {b, c} kaj la sendependa aro {a}
• kliko {b} kaj la sendependa aro {a, c}

Fendaj grafeoj povas esti karakterigitaj per iliaj konkluditaj subgrafeoj, grafeo estas fenda se kaj nur se neniu konkludita subgrafeo estas ciklo sur kvar aŭ kvin verticoj, aŭ paro de disaj lateroj (la komplemento de 4-ciklo).

Fendaj grafeoj estis unue studitaj de Földes kaj Hammer en du paperoj en 1977, kaj sendepende prezentitaj de Tiŝkeviĉ kaj Ĉernjak en 1979.