КАТЕГОРИИ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) П Архитектура- (3434) Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Война- (14632) Високи технологии- (1363) География- (913) Геология- (1438) 1065) House- (47672) Журналистика и масови медии- (912) Изобретения- (14524) Чужди езици- (4268) Компютри- (17799) Изкуство- (1338) История- (13644) Компютри- (11121 ) Художествена литература (373) Култура- (8427) Лингвистика- (374 ) Медицина- (12668 ) Naukovedenie- (506) Образование- (11852) Защита на труда- ( 3308) Педагогика- (5571) P Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Олимпиада- (1312) Политика- (7869) Право- (5454) Инструменти- ( 1369) Програмиране- (2801) Производство- (97182) Промишленост- (8706) Психология- (18388) Земеделие- (299) Социология- (6455) Спорт- (42831) Строителство- (4793) Търговия- (5050) Транспорт- (2929) Туризъм- (1568) Физика- (3942) ) Химия- (22929 ) Екология- (12095) Икономика- (9961) Електроника- (8441) Електротехника- (4623) Енергетика- (12629 )

Методи за графично представяне в аналитична форма

Вижте също:
  1. I. Предмет и методи на статистиката
  2. II Графоаналитични методи
  3. II. Специални методи за изследване на пациенти със съдови заболявания на долните крайници.
  4. III. Мерки и единици за представяне, измерване и съхранение на информация в компютър
  5. III. Изследователски методи в теорията на историческите науки
  6. III. Икономически и математически методи за изследване на междубраншовите отношения.
  7. IV. Визуални методи
  8. А-регулационни методи.
  9. A. Не-експериментални психологически методи
  10. Абразивност на скалите. Методи и схеми за изучаване на металното износване в взаимодействието със скалата.
  11. Разходи на агенцията и методи за тяхното намаляване
  12. Административни методи

Помислете за пример за изграждане на графика. Нека множеството върхове да бъде дефинирано като V = {a, b, c, d} и наборът от ръбовете като X = {1, 2, 3, ..., 7}. Нека случайната на графиката P да бъде дефинирана от девет стойности: P (a, 1, a); Р (а, 2, Ь); Р (b, 3, а); Р (а, 3, Ь); Р (а, 4, с); Р (а, 5, с); Р (с, 5, а); Р (с, 6, Ь); P (b, 7, c) - които са верни, останалите са неверни. Образът на графиката е представен на фиг. 4.8. В този пример върховете а, b и c са съседни и връх d е изолиран, т.е. не е инцидент с никакви ръбове.

1

и

3 б

4 5

г

в

Фиг. 4.8

Има и други начини за дефиниране на графики. Нека разгледаме друг пример: да се даде изображение на неопределена графика G (фигура 4.9а) и подобна digraph GO (фигура 4.9b). Нека v 1 , v 2 , ... v 5 са върхове и x 1 , x 2 , ... x 6 са ръбове (дъги). Графиките G и GO могат да бъдат представени в аналитична форма или чрез съседната матрица А, или матрицата на честотата В.

v 4 х 2 v 3 v 4 х 2 v 3

х 3 х 5 х 3 х 5

х 1 v 2 х 4 х 1 v 2 х 4

v 5 х 6 v 5 х 6

v 1 v 1

а) б)

Фиг. 4.9

Матрицата на честотата на графиката G е матрицата B = || b ij ||, с i = 1, .., n колони и j = 1, ..., m линии, които съответстват на броя върхове n и броя на ръбовете m. Елемент на матрицата b ij = 1, ако върхът v i е свързан с ръба x j и b ij = 0, ако не е инцидент. За насочена графика елементът на матрицата е b ij = 1, ако дъгата започва от върха и b ij = -1, ако дъгата е на върха. Ако има бримка в digraph, тогава b ij = 2. За нерегламентираната графика и digraph, представени на Фиг. 4.9а и б, матриците на разпространение са съответно, както следва:

v 1 , v 2 , v 3 , v 4 , v 5 v 1 , v 2 , v 3 , v 4 , v 5

1 1 0 0 0 х 1 1 -1 0 0 0 x 1

0 1 1 0 0 х 2 0 1 -1 0 0 х 2

B (g) = 0 1 1 0 0 х 3 В (G O ) = 0 -1 1 0 0 x 3

0 1 0 0 1 х 4 0 1 0 0 -1 х 4

0 0 1 0 1 х 5 0 0 -1 0 1 х 5

0 0 0 0 1 х 6 0 0 0 0 2 х 6

Във всеки ред на матрицата на случаите само два елемента (или един) са различни от нула. Матрицата на честотата може да се използва за определяне на градусите на всички върхове на графиката. В същото време за стойностите на буферите се удвоява.

Съседната матрица на графика G се нарича квадратна матрица А = || a ij ||, чиито колони и редове съответстват на върховете на графиката i = 1, ..., n ; j = 1, ..., n . За неподходяща графика елементът на матрицата a ij е равен на броя на краищата, достигащи до върховете v i и v j , за digraph е равен на броя на краищата с начало на върха v i и края на върха v j . За нашия пример ще има матрици на съседство

v 1 , v 2 , v 3 , v 4 , v 5 v 1 , v 2 , v 3 , v 4 , v 5

0 1 0 0 0 v 1 0 0 0 0 0 v 1

1 0 2 0 1 v 2 1 0 1 0 0 v 2

A (G) = 0 2 0 0 1 v 3 A (G O ) = 0 1 0 0 1 v 3



0 0 0 0 0 v 4 0 0 0 0 0 v 4

0 1 1 0 1 v 5 0 1 0 0 1 v 5

Както може да се види, матрицата на съседство за недиректна графика е симетрична и по избор за digraph. Графика със симетрична матрица на съседство канонично съответства на неграф със същата матрица на съседство.

Така че графиките могат да бъдат дефинирани по три начина:

1. Директно определяне на множествата от върхове V и ръбовете X, както и отношението на наклона.

2. Матрицата на съседство или матрицата на честотата.

3. Графично изображение (снимка).

Как да установим, че тези две графики са еднакви? За първите два начина за уточняване на отговора, отговорът е прост: когато техните описания са еднакви - списъци с върхове и ръбове или матрици. Според фигурата е по-трудно да се определи дали графиките са еднакви. Същата графика може да бъде представена от различни шаблони (фигура 4.10), като подреждат върховете по различни начини и придава на ръбовете различна геометрична форма и дължина. От друга страна, два привидно идентични модела могат да имат различни графики, ако имат различни номера на върха, поради което матриците на съседство и списъците на ръбовете ще бъдат различни (фиг.4.11).

Фиг. 4.10 Фиг. 4.11

Графики, които се различават само при номерирането на върховете (и които могат да бъдат направени еднакви с преномериране) се наричат изоморфни . Изоморфизмът на графики с малък брой върхове понякога е очевиден. Въпреки това, в общия случай, проблемът с установяването на изоморфизъм на графиките се оказва трудно изчислителна задача.

<== предишна лекция | следващата лекция ==>
| Методи за графично представяне в аналитична форма

; Дата на добавяне: 2014-01-07 ; ; Виждания: 366 ; Нарушение на авторски права? ;


Вашето мнение е важно за нас! Дали публикуваният материал е полезен? Да | не



ТЪРСЕНЕ ПО САЙТА:


Препоръчителни страници:

Вижте също:



ailback.ru - Edu Doc (2013 - 2018) година. Всички материали, представени на сайта само с цел запознаване с читателите и не извършват търговски цели или нарушаване на авторски права! Последно добавяне на IP: 11.45.9.156
Повторно генериране на страницата: 0.003 сек.