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

Задання графа за допомогою матриці інцидентності.

Прочитайте:
  1. Aлгоритмы на графах
  2. А допомогою якого методу визначають функціональну здатність нирок?
  3. Алгоритм обчислення за допомогою Microsoft Excel
  4. Вимкнути живлення.Переключити вхід осцилографа до виходу випрямляча.
  5. Відповідальність спеціалістів поліграфа
  6. Волновые процессы и разметка графа
  7. ДОСЛІДЖЕННЯ З ДОПОМОГОЮ МІКРОСКОПА
  8. Задання графа за допомогою матриці суміжності.
  9. Задання графа за допомогою списку.

 

Задати граф означає задати множини його вершин і ребер та відношення інцидентності. Коли граф G – скінчений його вершини та ребра нумерують: - вершини графа G; - його ребра. Відношення інциндентності можна задати матрицею E, що має m рядків і n стовпців. Елементи цієї матриці , , ;

 
 

Якщо ребро інцидентне вершині і в протилежному випадку. Ця матриця інцидентності звичайного графа є способом його визначення.

Рисунок 3.6 – Звичайний граф

Дещо по-іншому формується матриця інцидентності E для орієнтованого графа. Якщо -початок дуги, то , а якщо - кінець дуги, то . В тому випадку, коли -петля , де - число відмінне від 1,0 і -1.(Наприклад )

 
             
             
             
             
             
             
             
             
             
             
             
                 

 

 
 

Рисунок 3. 7 – Орієнтований граф (орграф).

 
-1            
-1            
  -1          
    -1        
    -1        
    -1        
            -2
  -1          

Матриця інцидентності.

 

 
 

Приклад. Скласти матрицю інцидентності для графа:

 

 

Рисунок 3. 8 - Мультиграф

 

 

 
       
       
       
       
       
       

 

 

 
       
       
       
       

 


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







При использовании материала ссылка на сайт medlec.org обязательна! (0.004 сек.)