Forbidden subgraph

Материал из WikiGrapp
Перейти к:навигация, поиск

Forbidden subgraph --- запрещенный подграф.

1. If H_{1},  \ldots,  H_{k} \; (k \geq 1) are graphs, then a graph G is said to be H_{1},  \ldots,  H_{k}-free if G contains no copy of any of the graphs H_{1},  \ldots,  H_{k} as an induced subgraph; the graphs H_{1}, \ldots, H_{k} will be also referred to in this context as forbidden subgraphs.

2. A cf-graph G with the initial node p_0 has a forbidden subgraph if there exist distinct nodes p_1,p_2 and p_3 and simple paths P_{0,1}, P_{1,2}, P_{1,3}, P_{2,3}, P_{3,2}, where P_{i,j} denotes a path from p_i to p_j, that do not intersect on internal nodes.