нека
и
- две наведнъж ориентирани или не-ориентирани графика с разединена определя продукта vershin.Pryamym
брои
Тя се нарича граф
с множество пикове, където дъга (край) от върха
към върха
съществува единствено и само ако съществува дъга (ребра)
и
в същото време.
Помислете за работата на директен продукт от графиките в матрична форма.
Teorema2.2.6. нека
и
- две наведнъж ориентирани или не-ориентирани графика с несвързани набори от върха,
- близост матрица на върховете, съответно. След това върховете на матрица графика близост е матрица на величина, при който елементът
, посочващ броя на ръбове (ръбове), които се свързват върха
с
, Тя се изчислява, както следва:
,
където
и
- елементите на матрицата
съответно,
,
.
MatritsyAravna измерение, както добре. По дефиниция, в графика
има дъга (край) като се започне от върха
към върха
, ако и само ако има дъга едновременно (ребра)
и
. Елемент близост матрица А grafaG
определя броя на ръбове (ръбове) на върховете
към върха
. Намирането на броя на дъгите (ръбове) на графики
и
, който в същото време
и
, Тя отговаря за експлоатацията на вземане на минималните елементи
и
матрици
съответно.
Следствие. Ако графики
и
не са няколко дъги (ръбове) и една линия на ненасочена графика не се счита за двойно, след изчисляване на елементите на матрицата близост на върховете
работа на вземане на минималната елемент съответства на обичайна изчисления или логичен продукт:
.
Забележка. За да се опрости и ускори процеса на изчисляване на матрицата елементи близост vershinAgrafa
Ние използваме следното наблюдение. приемем, че без ограничение на общността. Поръчайте колоните и редовете matritsyAsleduyuschim начин: След matritsuAmozhno разделени в
блокове, съответстващи на елементите на матрицата А1. размерност
. Елементът на всеки блок
fiksirovannyeiiki трябва да се изчислява като
, освен това
- фиксиран елемент на матрица А1. Ако елементите на матрици А1 и А2 са като само стойности 0 и 1, а след това - Direct (тензор) матрица продукт:
където
умножена по скаларна матрица А2.
е 0, ако
, и е равно на А2. ако
.
Primer2.2.6. Операцията е директен продукт на графики, показани на фиг. 2.2.12.
Очевидно е, че кореспонденцията между елементите на наборите
и
Тя определя изоморфизъм на графики
и
, което е вярно в общия случай.
Форма върховете на съседство матрица първоначалните обвинения и.
,
.
Според следствие на теорема 2.2.6 и забележка близост матрицата на върховете
Това е, както следва:
Лесно е да се провери, че съседството матрицата на съответства на броя на връх
, е показана на Фиг. 2.2.12.
Експлоатация на директен продукт от графики има следните свойства, които са резултат от определението, както и свойства на декартово произведение на комплекта и са валидни за всяка ориентирани или не ориентиран едновременно графики
с несвързани групи от върховете:
Действието на директен продукт може да бъде удължен чрез индукция и да е ограничен набор от насочени или неориентирани графа с несвързани набори от върховете:
.
Свързани статии
