Graf skæringspunkt

Grafskæring er en operation på grafer , der resulterer i en graf, hvis top- og kantsæt er skæringspunkterne mellem top- og kantsættene for de originale grafer. Med andre ord inkluderer den resulterende graf kun de kanter og de hjørner, der er til stede i alle de originale grafer [1] .

Operationen af ​​skæringspunktet for grafer, såvel som en lignende operation for sæt, er normalt angivet med symbolet :

Således, hvis

derefter

hvor er sættet af hjørner, er sættet af kanter på grafen.

Se også

• Ordliste over grafteoretiske termer
• grafteori
• Sammenslutning af grafer

Noter

1. ↑ Swami M. (1984), s. 21.

Links

• Swami M., Thulasiraman K. Grafer, netværk, algoritmer: Pr. fra engelsk. — M.: Mir, 1984. — 455 s.
• Harari F. Grafteori. — M.: Mir , 1973.
• Diskret matematik: Algoritmer, grafvisualisering, applets