Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Постановка лабораторной работы по теоии графов (алгоритмы и программы)" Страница 1

(Назад) (Cкачать работу)

Ïîñòàíîâêà ëàáîðàòîðíîé ðàáîòû ïî òåîðèè ãðàôîâ

(àëãîðèòìû è ïðîãðàììû) 1. Ââåäåíèå  ïîñëåäíåå âðåìÿ èññëåäîâàíèÿ â îáëàñòÿõ, òðàäèöèîííî îòíîñÿùèõñÿ ê äèñêðåòíîé ìàòåìàòèêå, çàíèìàþò âñå áîëåå çàìåòíîå ìåñòî. Íàðÿäó ñ òàêèìè êëàññè÷åñêèìè ðàçäåëàìè ìàòåìàòèêè, êàê ìàòåìàòè÷åñêèé àíàëèç, äèôôåðåíöèàëüíûå óðàâíåíèÿ, â ó÷åáíûõ ïëàíàõ ñïåöèàëüíîñòè "Ïðèêëàäíàÿ ìàòåìàòèêà" è ìíîãèõ äðóãèõ ñïåöèàëüíîñòåé ïîÿâèëèñü ðàçäåëû ïî ìàòåìàòè÷åñêîé ëîãèêå, àëãåáðå, êîìáèíàòîðèêå è òåîðèè ãðàôîâ. Ïðè÷èíû ýòîãî íåòðóäíî ïîíÿòü, ïðîñòî îáîçíà÷èâ êðóã çàäà÷, ðåøàåìûõ íà áàçå ýòîãî ìàòåìàòè÷åñêîãî àïïàðàòà (ñì. ï.1.3 äàííîãî ðàçäåëà).

1.1 Îñíîâíûå ïîíÿòèÿ òåîðèè ãðàôîâ. Äåòàëüíûå îïðåäåëåíèÿ òåîðèè ãðàôîâ ìîæíî íàéòè â ðàáîòàõ [2, 3, 4, 5, 6]. Çäåñü ìû ëèøü îãðàíè÷èìñÿ ïåðå÷èñëåíèåì íåêîòîðûõ òåðìèíîâ, êîòîðûå áóäóò âñòðå÷àòüñÿ â äàëüíåéøåì, è èõ êðàòêèì îïèñàíèåì.

Ãðàô- íåïóñòîå ìíîæåñòâî V è X- íåêîòîðûé íàáîð ïàð ýëåìåíòîâ èç V. Ýëåìåíòû ìíîæåñòâà V íàçûâàþòñÿ âåðøèíàìè, à ýëåìåíòû íàáîðà X- ðåáðàìè.

Ïîäãðàô- ïîäãðàôîì ãðàôà G íàçûâàåòñÿ ãðàô, âñå âåðøèíû è ðåáðà êîòîðîãî ñîäåðæàòñÿ ñðåäè âåðøèí è ðåáåð ãðàôà G. Îñòîâíûé ïîäãðàô ñîäåðæèò âñå âåðøèíû ãðàôà G.

Ñâÿçíûé ãðàô- ãðàô, ó êîòîðîãî äëÿ ëþáûõ äâóõ ðàçëè÷íûõ âåðøèí ñóùåñòâóåò öåïü (ïîñëåäîâàòåëüíîñòü ñìåæíûõ âåðøèí), ñîåäèíÿþùàÿ èõ.

Âçâåøåííûé ñâÿçíûé ãðàô- ñâÿçíûé ãðàô, ñ çàäàííîé âåñîâîé ôóíêöèåé (êàæäîìó ýëåìåíòó íàáîðà X ñòàâèòñÿ â ñîîòâåòñòâèå íåêîòîðîå ÷èñëî - âåñ ðåáðà).

Äåðåâî- ñâÿçíûé ãðàô, íå ñîäåðæàùèé öèêëîâ.

Îñòîâ- îñòîâíûé ïîäãðàô, ÿâëÿþùèéñÿ äåðåâîì.

1.2 Ñïîñîáû çàäàíèÿ ãðàôîâ. Ñóùåñòâóåò ðÿä ñïîñîáîâ çàäàíèÿ ãðàôîâ. Äëÿ ðåøåíèÿ êîíêðåòíîé çàäà÷è ìîæíî âûáðàòü òîò èëè èíîé ñïîñîá, â çàâèñèìîñòè îò óäîáñòâà åãî ïðèìåíåíèÿ. Çäåñü ìû ïåðå÷èñëèì íåêîòîðûå, íàèáîëåå èçâåñòíûå ñïîñîáû, äàäèì èõ êðàòêóþ õàðàêòåðèñòèêó ñ òî÷êè çðåíèÿ óäîáñòâà ââîäà è îáðàáîòêè íà ÝÂÌ.

Ìàòðèöà èíöèäåíòíîñòè- ìàòðèöà ðàçìåðîì µ § (n- ÷èñëî âåðøèí, m- ÷èñëî ðåáåð), ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ âåðøèíà èíöèäåíòíà j-ìó ðåáðó, è 0 â ïðîòèâíîì ñëó÷àå.

Ìàòðèöà èíöèäåíòíîñòè íåóäîáíà äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ, êðîìå òîãî îíà íå íåñåò ïðÿìîé èíôîðìàöèè î ðåáðàõ.

Ìàòðèöà ñìåæíîñòè- ìàòðèöà ðàçìåðîì µ §, ýëåìåíòû êîòîðîé ðàâíû 1, åñëè i-ÿ âåðøèíà ñìåæíà ñ j-îé, è 0 â ïðîòèâíîì ñëó÷àå.

Ìàòðèöà ñìåæíîñòè ÿâëÿåòñÿ ñèììåòðè÷íîé è äîñòàòî÷íî ïðîñòî ìîæåò èñïîëüçîâàòüñÿ äëÿ ââîäà è îáðàáîòêè íà ÝÂÌ. Äëÿ ñëó÷àÿ âçâåøåííîãî ãðàôà âìåñòî 1 èñïîëüçóåòñÿ çíà÷åíèå âåñîâîé ôóíêöèè è òàêàÿ ìàòðèöà íàçûâàåòñÿ ìàòðèöåé âåñîâ.

Ñïèñêè ñìåæíîñòè- êàæäûé i-é ñïèñîê ñîäåðæèò íîìåðà âåðøèí, ñìåæíûõ i-îé âåðøèíå.

Ñïèñêè ñìåæíîñòè óäîáíû äëÿ ââîäà â ÝÂÌ, ýêîíîìÿò ïàìÿòü, íî íå ìîãóò èñïîëüçîâàòüñÿ â ñëó÷àå âçâåøåííîãî ãðàôà.

1.3 Îáçîð çàäà÷ òåîðèè ãðàôîâ. Ðàçâèòèå òåîðèè ãðàôîâ â îñíîâíîì îáÿçàíî áîëüøîìó ÷èñëó âñåâîçìîæíûõ ïðèëîæåíèé. Ïî-âèäèìîìó, èç âñåõ ìàòåìàòè÷åñêèõ îáúåêòîâ ãðàôû çàíèìàþò îäíî èç ïåðâûõ ìåñò â êà÷åñòâå ôîðìàëüíûõ ìîäåëåé ðåàëüíûõ ñèñòåì.

Ãðàôû íàøëè ïðèìåíåíèå ïðàêòè÷åñêè âî âñåõ îòðàñëÿõ íàó÷íûõ çíàíèé: ôèçèêå, áèîëîãèè, õèìèè, ìàòåìàòèêå, èñòîðèè, ëèíãâèñòèêå, ñîöèàëüíûõ íàóêàõ, òåõíèêå è ò.ï. Íàèáîëüøåé ïîïóëÿðíîñòüþ òåîðåòèêî-ãðàôîâûå ìîäåëè èñïîëüçóþòñÿ ïðè èññëåäîâàíèè

Похожие работы