Индекс компонент

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

Индекс компонент (Component index) — (относительно простой цепи \,L) число компонент связности в графе G
\setminus L, получающемся из исходного графа \,G удалением всех вершин цепи \,L и всех инцидентных им ребер. Индекс компонент относительно множества вершин \,A — это число компонент связности в графе, получаемом из исходного удалением вершин из множества \,A и всех инцидентных им ребер.

Литература

  • Оре О. Теория графов. — М.: Наука, 1968.