АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Локальні степені вершин графа

Кількість ребер, які інцидентні вершини , називають локальною степеню вершини графа. Якщо задані матриці інцидентності E або суміжності , то можна визначити локальні степені вершин графа. Дійсно, якщо ребро інцидентне вершини то на перетині -го рядка і -го стовпця маємо 1. В іншому випадку матимемо 0.

Отже, = За матрицею інцидентності (2.1)

Елементи матриці суміжності – це кількість ребер, інцидентних вершинам і .

Звідси = .

Наведені формули справедливості для підрахунку локальної степені (ЛС) вершин графів без петель. У тому випадку коли граф має петлі ЛС вершин графа знаходять за такою формулою(використовується матриця інцидентності).

, де - кількість рядків матриці, - кількість стовпців матриці.

Дійсно, коли ребро звичайне (з’єднує дві вершини),то .

Якщо ж воно є петлею, то і відповідно , тобто 2 для петель інцидентних вершині і 0 для інших вершин.

Якщо для визначення ЛС вершин графа використовується таблиця суміжностей, то для цієї мети використовується така формула:

Означення 1. Граф називається однорідним степеня k, якщо степені всіх його вершин рівні між собою і дорівнюють k.

Якщо однорідний граф має n вершин і m ребер, то

приклад:

однорідний граф (k=3)

n=4;

Означення 2. Звичайний граф називається повним, якщо кожна пара його вершин з’єднана ребром.

Дата добавления: 2015-09-27 | Просмотры: 821 | Нарушение авторских прав