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