Частичные графы и подграфы

Граф над частичным для если для всех X где отображение вершин X в множестве, а - множество вершин в отображении вершин графа

Если частичный граф, графа G, то и все его ребра явлений ребрами графа G, обратное утверждение не верно, то есть в G могут быть ребра не оринадл H.

Нуль граф является частичным для любого графа

(рисунок) (рисунок) (рисунок)

Отсюда следует, что ребрами полуграфа Г со знаком А является все ребара Г, оба конца которого принадлежат А.

(рисунок)

Для вершины , в переходном графе

Чтобы построить подграфа надо взять некоторые из вершин и все ребра исходного графа. Граф

Представим что у нас есть матрицв смежности 2-х графов умноженных само на себя

Если то элемент указываем число различных путей n длины n ведущиз из вершины G

Поиск по сайту: