Ìàòðèöà èíöèäåíòíîñòè- ìàòðèöà ðàçìåðîì (n- ÷èñëî âåðøèí, m- ÷èñëî ðåáåð), ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ âåðøèíà èíöèäåíòíà j-ìó ðåáðó, è 0 â ïðîòèâíîì ñëó÷àå.
Ìàòðèöà èíöèäåíòíîñòè íåóäîáíà äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ, êðîìå òîãî îíà íå íåñåò ïðÿìîé èíôîðìàöèè î ðåáðàõ.
Ìàòðèöà ñìåæíîñòè- ìàòðèöà ðàçìåðîì , ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ âåðøèíà ñìåæíà ñ j-îé, è 0 â ïðîòèâíîì ñëó÷àå.
Ìàòðèöà ñìåæíîñòè ÿâëÿåòñÿ ñèììåòðè÷íîé è äîñòàòî÷íî ïðîñòî ìîæåò èñïîëüçîâàòüñÿ äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ. Äëÿ ñëó÷àÿ âçâåøåííîãî ãðàôà âìåñòî 1 èñïîëüçóåòñÿ çíà÷åíèå âåñîâîé ôóíêöèè è òàêàÿ ìàòðèöà íàçûâàåòñÿ ìàòðèöåé âåñîâ.
Ñïèñêè ñìåæíîñòè- êàæäûé i-é ñïèñîê ñîäåðæèò íîìåðà âåðøèí, ñìåæíûõ i-îé âåðøèíå.
Ñïèñêè ñìåæíîñòè óäîáíû äëÿ ââîäà â ÝÂÌ, ýêîíîìÿò ïàìÿòü, íî íå ìîãóò èñïîëüçîâàòüñÿ â ñëó÷àå âçâåøåííîãî ãðàôà.
1.3 Îáçîð çàäà÷ òåîðèè ãðàôîâ.
Ðàçâèòèå òåîðèè ãðàôîâ â îñíîâíîì îáÿçàíî áîëüøîìó ÷èñëó âñåâîçìîæíûõ ïðèëîæåíèé. Ïî-âèäèìîìó, èç âñåõ ìàòåìàòè÷åñêèõ îáúåêòîâ ãðàôû çàíèìàþò îäíî èç ïåðâûõ ìåñò â êà÷åñòâå ôîðìàëüíûõ ìîäåëåé ðåàëüíûõ ñèñòåì.
Ãðàôû íàøëè ïðèìåíåíèå ïðàêòè÷åñêè âî âñåõ îòðàñëÿõ íàó÷íûõ çíàíèé: ôèçèêå, áèîëîãèè, õèìèè, ìàòåìàòèêå, èñòîðèè, ëèíãâèñòèêå, ñîöèàëüíûõ íàóêàõ, òåõíèêå è ò.ï. Íàèáîëüøåé ïîïóëÿðíîñòüþ òåîðåòèêî-ãðàôîâûå ìîäåëè èñïîëüçóþòñÿ ïðè èññëåäîâàíèè êîììóíèêàöèîííûõ ñåòåé, ñèñòåì èíôîðìàòèêè, õèìè÷åñêèõ è ãåíåòè÷åñêèõ ñòðóêòóð, ýëåêòðè÷åñêèõ öåïåé è äðóãèõ ñèñòåì ñåòåâîé ñòðóêòóðû.
Äàëåå ïåðå÷èñëèì íåêîòîðûå òèïîâûå çàäà÷è òåîðèè ãðàôîâ è èõ ïðèëîæåíèÿ:
- Çàäà÷à î êðàò÷àéøåé öåïè
çàìåíà îáîðóäîâàíèÿ
ñîñòàâëåíèå ðàñïèñàíèÿ äâèæåíèÿ òðàíñïîðòíûõ ñðåäñòâ
ðàçìåùåíèå ïóíêòîâ ñêîðîé ïîìîùè
ðàçìåùåíèå òåëåôîííûõ ñòàíöèé
- Çàäà÷à î ìàêñèìàëüíîì ïîòîêå
Страницы: 1, 2, 3, 4, 5, 6, 7
