Чиглүүлсэн график өгөгдсөн. Баримтлагдсан график. Давтсан график, холимог график, хоосон график, мультиграф, энгийн график, бүрэн график

Чиглүүлсэн график(товчхон диграф) нь ирмэгүүд нь чиглэл өгсөн (олон) график юм. Чиглүүлсэн ирмэгийг мөн нэрлэдэг нумууд, мөн зарим эх сурвалжид зөвхөн ирмэгүүд. Ирмэг нь чиглэл өгөөгүй графикийг чиглүүлээгүй график буюу эсвэл диграфгүй.

Үндсэн ойлголтууд

Албан ёсоор диграф D = (V , E) (\displaystyle D=(V,E))олон хэсгээс бүрддэг V (\displaystyle V), тэдгээрийн элементүүдийг нэрлэдэг оргилууд, ба багц E (\displaystyle E)захиалсан хос орой u , v ∈ V (\displaystyle u,v\in V).

Нуман (u , v) (\displaystyle (u,v)) тохиолдлыноргилууд u (\displaystyle u)болон v (\displaystyle v). Үүний зэрэгцээ тэд ингэж хэлдэг u (\displaystyle u) - анхны оргилнумууд, ба v (\displaystyle v) - терминалын оргил.

Холболт

Маршрутдиграф дахь оройн ээлжийн дараалал гэж нэрлэдэг ба нумууд, эелдэг v 0 (v 0, v 1) v 1 (v 1, v 2) v 2. . . v n (\displaystyle v_(0)\(v_(0),v_(1)\)v_(1)\(v_(1),v_(2)\)v_(2)...v_(n))(оройнуудыг давтаж болно). Маршрутын урт- доторх нумын тоо.

Замбайдаг маршрутнумуудыг давтахгүйгээр диграф хэлбэрээр, хялбар арга- давтагдах орой байхгүй. Хэрэв нэг оройгоос нөгөө орой руу хүрэх зам байгаа бол хоёр дахь орой хүрэх боломжтойэхний үеэс.

Хэлхээхаалттай байна зам.

Учир нь хагас замнумын чиглэлийн хязгаарлалтыг арилгаж, хагасболон хагас контур.

диграф хүчтэй холбогдсон, эсвэл зүгээр л хүчтэй, хэрэв түүний бүх оройнууд харилцан байвал хүрэх боломжтой; нэг талын холбогдсон, эсвэл зүгээр л нэг талынхэрэв аль нэг хоёр оройн дор хаяж нэг нь нөгөөгөөсөө хүрэх боломжтой бол; сул холбогдсон, эсвэл зүгээр л сул, хэрэв нумын чиглэлийг үл тоомсорловол холбогдсон (олон) графикийг олж авна;

Хамгийн их хүчтэйдэд хэсэг гэж нэрлэдэг хүчтэй бүрэлдэхүүн хэсэг; нэг талын бүрэлдэхүүн хэсэгболон сул бүрэлдэхүүн хэсэгижил төстэй байдлаар тодорхойлогддог.

конденсацдиграф D (\displaystyle D)орой нь хүчтэй бүрэлдэхүүн хэсэг болох диграф гэж нэрлэдэг D (\displaystyle D), ба нум дотор D ⋆ (\displaystyle D^(\од))харгалзах бүрэлдэхүүн хэсгүүдэд багтсан оройнуудын хооронд дор хаяж нэг нум байгааг харуулж байна.

Нэмэлт тодорхойлолтууд

Чиглүүлсэн ациклик графикэсвэл гамакконтургүй диграф юм.

Ирмэгүүдийн чиглэлийг өөрчлөх замаар өгөгдсөн графикаас гаргаж авсан чиглүүлсэн график гэж нэрлэдэг урвуу.

Гурван зангилаа бүхий бүх диграфын зураг ба шинж чанарууд

Домог: FROM- сул дорой, OS- нэг талт, SS- хүчтэй, Х- чиглэлтэй график, Г- гамак (цикл), Т- тэмцээн

0 нум	1 нум	2 нуман	3 нум	4 нум	5 нум	6 нуман
хоосон, Н, Г	Н, Г		OS	CC	CC	бүрэн, CC
		ОС, Н, Г	CC, N, T	CC
		Ц, Н, Г	OS, N, G, T	OS
		Ц, Н, Г	OS

Өмнөх бүлгүүдэд бид чиглүүлэлтгүй графикийн онолын зарим үндсэн үр дүнг танилцуулсан. Гэсэн хэдий ч, чиглүүлэлтгүй график нь зарим нөхцөл байдлыг тайлбарлахад хангалтгүй юм. Жишээлбэл, гудамжны ирмэгүүдтэй таарч байгаа график бүхий замын хөдөлгөөний зургийг дүрслэхдээ хөдөлгөөний зөвшөөрөгдөх чиглэлийг заах ирмэгүүдэд чиг баримжаа олгох ёстой. Өөр нэг жишээ бол ирмэгүүд нь нэг заавраас нөгөөд шилжих удирдлагын урсгалыг илэрхийлдэг графикаар загварчилсан компьютерийн программ юм. Програмын энэ дүрслэлд хяналтын урсгалын чиглэлийг зааж өгөхийн тулд ирмэгүүд нь чиг баримжаа өгөх ёстой. Төлөөлөхийн тулд чиглэсэн график шаардлагатай физик системийн өөр нэг жишээ бол цахилгаан хэлхээ юм. Чиглүүлсэн график болон холбогдох алгоритмуудын хэрэглээг Бүлэгт авч үзнэ. 11-15.

Энэ бүлэгт чиглэсэн графикийн онолын үндсэн үр дүнг харуулав. Баримтлагдсан Эйлерийн гинж ба Гамильтоны мөчлөгтэй холбоотой асуултуудыг авч үзсэн болно. Баримтлагдсан мод ба тэдгээрийн Эйлерийн чиг баримжаатай хэлхээ холбоог мөн авч үздэг.

5.1. Үндсэн тодорхойлолт ба ойлголтууд

Заасан графиктай холбоотой зарим үндсэн тодорхойлолт, ойлголтуудыг танилцуулж эхэлцгээе.

Чиглүүлсэн график нь хоёр олонлогоос бүрдэнэ: элементүүдийг нь орой гэж нэрлэдэг төгсгөлтэй V олонлог, элементүүдийг нь ирмэг буюу нум гэж нэрлэдэг төгсгөлтэй E олонлог. Нуман бүр нь дараалсан хос оройтой холбоотой байдаг.

Оройг тэмдэглэхэд тэмдэг, нумыг тэмдэглэхэд тэмдэг хэрэглэнэ. Хэрэв , дараа нь төгсгөлийн орой гэж нэрлэгддэг, энд - эхний орой, - төгсгөлийн орой . Эхлэх ба төгсгөлийн хос оройтой бүх нумуудыг параллель гэж нэрлэдэг. Хэрэв ослын орой нь түүний эхлэл ба төгсгөлийн орой бол нумыг гогцоо гэж нэрлэдэг.

Чиглүүлсэн графикийн график дүрслэлд оройг цэгүүд эсвэл тойрог хэлбэрээр, ирмэгийг (нумыг) сегментээр дүрсэлдэг.

цэгүүдийг холбосон шугамууд эсвэл тэдгээрийн төгсгөлийн цэгүүдийг дүрсэлсэн тойрог. Нэмж дурдахад, нумануудад чиг баримжаа олгох бөгөөд энэ нь эхлэлийн оройноос төгсгөлийн орой руу чиглэсэн сумаар тодорхойлогддог.

Жишээлбэл, хэрэв тэднийх байвал чиглэсэн графикийг 1-р зургаар дүрсэлж болно. 5.1. Энэ график дээр - зэрэгцээ нумууд ба - гогцоо.

Цагаан будаа. 5.1. Баримтлагдсан график.

Нуман нь төгсгөлийн орой руугаа тусдаг гэж хэлдэг. Нэг нумын төгсгөл бол оройг зэргэлдээ гэж нэрлэдэг. Хэрэв нумууд нь нийтлэг төгсгөлийн оройтой бол тэдгээрийг зэргэлдээ гэж нэрлэдэг.

Нумыг эхний оройноосоо гарч, эцсийн оройдоо орох гэж нэрлэдэг. Орой нь ослын нум байхгүй бол тусгаарлагдсан гэж нэрлэдэг.

Оройн зэрэг нь түүнд тохиолдсон нумын тоо юм. Оройн зэрэг нь V] руу орох нумын тоо, гаднах зэрэг нь гарах нумын тоо юм. Тэмдэгтүүд болон b" нь чиглүүлсэн графикийн хамгийн бага гадагш болон градусыг илэрхийлнэ. Үүний нэгэн адил тэмдэгтүүд нь тус тусын хамгийн их гаднах болон градусыг заана.

Аливаа оройн олонлогуудыг дараах байдлаар тодорхойлно: . Жишээлбэл, Зураг дээрх графикт. 5.1.

Гогцоо нь энэ оройн оролт, гарцын хагас градусыг нэмэгдүүлнэ гэдгийг анхаарна уу. Дараах баталгаа нь нум бүр нь чиглэсэн графикийн оролт ба гаралтын хагас градусын нийлбэрээр 1-ээр нэмэгддэг гэсэн үр дагавар юм.

Теорем 5.1. Нумантай чиглэсэн графикт

Дотор градусын нийлбэр = Гадны градусын нийлбэр = м.

Чиглүүлсэн графикийн дэд графикууд болон үүсгэсэн дэд графикууд нь чиглүүлэлтгүй графиктай адил тодорхойлогддог (1.2-р хэсэг).

G чиглэлтэй графын нумуудаас чиг баримжаа арилгасны үр дүнд үүссэн чиглүүлээгүй графикийг үндсэн чиглүүлэлтгүй граф G гэж нэрлэх ба -аар тэмдэглэнэ.

Чиглүүлсэн графикийн чиглүүлсэн зам нь оройнуудын төгсгөлтэй дараалал юм

Графикийн нум гэж юу вэ.Ийм замыг ихэвчлэн чиглүүлсэн -маршрут гэж нэрлэдэг ба эхний орой нь замын эцсийн орой бөгөөд бусад бүх орой нь дотоод байна. Чиглүүлсэн замын эхлэл ба төгсгөлийн оройг төгсгөлийн орой гэж нэрлэдэг. Чиглүүлсэн замд нумууд, улмаар оройнууд нэгээс олон удаа гарч ирж болохыг анхаарна уу.

Баримтлагдсан маршрутыг төгсгөлийн оройнууд нь өөр бол нээлттэй, үгүй ​​бол хаалттай гэж нэрлэдэг.

Баримтлагдсан замыг бүх нумууд нь ялгаатай бол чиглүүлсэн зам гэнэ. Баримтлагдсан зам нь төгсгөлийн цэгүүд нь ялгаатай бол нээлттэй, үгүй ​​бол хаалттай байна.

Нээлттэй чиг баримжаатай замыг бүх орой нь ялгаатай бол чиглүүлсэн зам гэнэ.

Хаалттай чиглэсэн гинжийг төгсгөлийн цэгүүдээс бусад оройнууд нь өөр өөр байвал чиглүүлсэн мөчлөг буюу контур гэж нэрлэдэг.

Чиглүүлсэн график нь контургүй бол цикл бус эсвэл контургүй гэж нэрлэгддэг. Жишээлбэл, 1-р зурагт чиглэсэн график нь цикл бус байна. 5.2.

Цагаан будаа. 5.2. Циклик чиглэсэн график.

Цагаан будаа. 5.3. Хүчтэй холбогдсон чиглүүлсэн график.

Чиглүүлсэн граф G-ийн оройнуудын дарааллыг G-ийн зам гэж нэрлэнэ.Хэрэв энэ нь үндсэн чиглүүлэггүй график дахь зам юм.Жишээ нь, Зураг дээрх график дахь дараалал. 5.2 нь маршрут боловч чиглээгүй.

Чиглүүлсэн графикийн гинж, зам, мөчлөгийг ижил төстэй байдлаар тодорхойлдог.

Хэрэв үндсэн чиглүүлэлтгүй график холбогдсон бол чиглэсэн графикийг холбогдсон гэж нэрлэдэг.

Чиглүүлсэн граф G-ийн дэд график нь графын бүрэлдэхүүн хэсэг бол G графикийн бүрэлдэхүүн хэсэг гэнэ.

G-ээс буцах чиглэлтэй зам байгаа бол G чиглэлтэй графын оройг хүчтэй холбосон гэж нэрлэдэг. Хэрэв хүчтэй холбогдсон бол --тэй хүчтэй холбогдсон нь ойлгомжтой. Орой бүр өөртэйгээ нягт холбоотой байдаг.

Хэрэв орой нь оройтой хүчтэй холбогдсон бол харахад хялбар байдаг тул орой нь оройтой хүчтэй холбогдсон байна.Тиймээс энэ тохиолдолд оройнууд нь хүчтэй холбогдсон гэж зүгээр л хэлнэ.

Хэрэв чиглүүлсэн графын бүх орой нь хүчтэй холбогдсон бол түүнийг хүчтэй холбосон гэж нэрлэдэг. Жишээлбэл, Зураг дээрх график. 5.3.

Чиглүүлсэн график G-ийн хамгийн их хүчтэй холбогдсон дэд графикийг G-ийн хүчтэй холбогдсон бүрэлдэхүүн хэсэг гэнэ. Хэрэв чиглүүлсэн график хүчтэй холбогдсон бол тэр нь өөрөө хүчтэй холбогдсон нэг бүрэлдэхүүн хэсэгтэй байна.

Чиглүүлсэн графикийг авч үзье. Түүний орой бүр нь G графикийн яг нэг хүчтэй холбогдсон бүрэлдэхүүн хэсэгт хамаарах болохыг хялбархан харж болно. Иймд хүчтэй холбогдсон бүрэлдэхүүн хэсгүүдийн оройн багцууд нь графикийн Y оройн олонлогийн хуваалтыг үүсгэдэг.

Цагаан будаа. 5.4. График ба түүний конденсац.

Жишээлбэл, Зураг дээрх чиглэсэн график. 5.4, ​​a нь оройн олонлог бүхий хүчтэй холбогдсон гурван бүрэлдэхүүн хэсэгтэй бөгөөд чиглэсэн графикийн оройн олонлогийн хуваалтыг бүрдүүлдэг.

Сонирхолтой нь, чиглэсэн график нь графикийн хүчтэй холбогдсон бүрэлдэхүүн хэсгүүдэд ороогүй нумуудыг агуулж болно. Жишээ нь, ямар ч хүчтэй холбогдсон бүрэлдэхүүн хэсэг нь Зураг дээрх графикт нумуудыг оруулаагүй болно. 5.4, ​​а.

Иймээс "хүчтэй холбогдсон" шинж чанар нь графикийн оройн олонлогийг хуваахыг шаарддаг ч нумын багцыг хуваахыг үүсгэхгүй байж магадгүй юм.

Чиглүүлсэн график дээрх нэгдэл, огтлолцол, mod 2 нийлбэр болон бусад үйлдлүүд нь чиглүүлэлтгүй графиктай яг ижил аргаар тодорхойлогддог (1.5-р хэсэг).

Чиглүүлсэн график G-ийн хүчтэй холбогдсон бүрэлдэхүүн хэсгүүдийн бүх нумын агшилтын үр дүнд үүссэн графикийг G-ийн конденсацын график гэж нэрлэдэг. Зурагт үзүүлсэн графикийн конденсац. 5.4, ​​a, зурагт үзүүлэв. 5.4б.

Графикийн оройнууд нь G графикийн хүчтэй холбогдсон бүрэлдэхүүн хэсгүүдтэй тохирч байх ба бүрэлдэхүүн хэсгүүдийн хураангуй дүрс гэж нэрлэдэг.

Чиглүүлсэн графын зэрэглэл ба цикломатик тоо нь харгалзах чиглүүлээгүй графынхтай ижил байна. Энэ нь хэрэв чиглэсэн график G нь нум, орой, бүрэлдэхүүн хэсгүүдтэй бол G графикийн зэрэглэл ба цикломатик тоог дараах байдлаар өгнө гэсэн үг юм.

Одоо бид хамгийн бага холбогдсон чиглэсэн графикуудыг тодорхойлж, тэдгээрийн зарим шинж чанарыг судалж байна.

Чиглүүлсэн график G нь хүчтэй холбогдсон бол хамгийн бага холболттой гэж хэлэх ба аливаа нумыг арилгах нь түүнийг хүчтэй холбогдсон шинж чанараас нь хасдаг.

Цагаан будаа. 5.5. Хамгийн бага холбогдсон чиглүүлсэн график.

Хамгийн бага холболт нь жишээлбэл, Зураг дээр үзүүлсэн график юм. 5.5.

Мэдээжийн хэрэг, хамгийн бага холбогдсон графикууд нь зэрэгцээ нуман болон гогцоотой байж болохгүй.

Чиглэлгүй график нь мод байвал л хамгийн бага холбогддог гэдгийг бид мэднэ (Жишээ нь 2.13). Теорем 2.5-д зааснаар мод нь 1-р зэрэглэлийн хоёроос багагүй оройтой байна.Иймд хамгийн бага холбогдсон чиглүүлэггүй графикууд нь 1-р зэргийн хоёроос багагүй оройтой байна.

Чиглүүлсэн графикуудын хувьд ижил төстэй үр дүнг тогтооцгооё. Хүчтэй холбогдсон чиглүүлсэн графын орой бүр нь гарах болон ирж буй нумтай байх тул хамгийн багадаа 2 байх ёстой. Дараах теоремоор бид хамгийн бага холбогдсон чиглүүлсэн график дор хаяж 2-р зэргийн хоёр оройтой болохыг баталж байна.

Эхний хичээл дээр графикийн тухай ойлголтыг танилцуулахдаа бид спортын багуудын тэмцээнийг жишээ болгон авч үзсэн. Бид. Эдгээр багууд аль хэдийн хоорондоо тоглож байсан тохиолдолд А ба С гэх хоёр багийг AC ирмэгтэй холбосон. Гэсэн хэдий ч ийм график нь нэг чухал асуултанд хариулдаггүй: хэн яг энэ тоглолтонд хожсон бэ?
Энэ дутагдлыг амархан арилгах боломжтой. Хэрэв А баг С-г хожсон бол бид А-аас С руу чиглэсэн АС-ийн ирмэг дээр сум тавихыг зөвшөөрнө. Бид аль хэдийн тоглосон бүх тоглолтын үр дүнг мэдэж байна гэж үзээд график дээр нэмээрэй. 1 харгалзах сум; Үүний үр дүнг Зураг дээр үзүүлсэн графикт үзүүлье. 58.

Зураг 58.

Энэ графикаас харахад А баг С, F баг А-д хожигдсон, В баг C, E, F гэх мэт бүх тоглолтод хожсон байна.

Ирмэгграфик гэж нэрлэдэг чиглэсэн, хэрэв нэг оройг авч үзвэл хавирганы эхлэл, нөгөө нь - Төгсгөл.
Бүх ирмэгүүд нь чиглэсэн графикийг нэрлэдэг чиг баримжаатоолох.
Чиглүүлсэн графын ижил орой нь зарим ирмэгүүдийн эхлэл, заримынх нь төгсгөл болж чаддаг. Үүний дагуу дээд талын хоёр градусыг ялгадаг. гарах зэрэг, элсэлтийн зэрэг.
Гарах зэрэгЧиглүүлсэн графикийн А орой нь А цэгээс гарах ирмэгүүдийн тоо юм (тэмдэглэгээ: d+(A)).
Чиглүүлсэн графикийн А оройн оролтын зэрэг нь оруулгын тоо юм ГЭХДЭЭирмэгүүд (тэмдэг: d-(A)).
Тоглолт тэнцээгээр дууссан бол яах вэ? Харгалзах ирмэгийг чиглүүлээгүй орхисноор бид тэнцсэн үр дүнг график дээр тусгаж болно. Ингэхдээ бид нэрлэсэн зүйлийг олж авдаг смШанни тоо, энэ нь чиглүүлсэн болон чиглээгүй ирмэгүүдтэй.
Чиглүүлсэн график дахь зам A1-ээс An хүртэлх G нь чиглэсэн ирмэгүүдийн дараалал юм<А1; А2>, <А2; А3>, ..., <Аn-1; Аn>, өмнөх ирмэг бүрийн төгсгөл нь дараагийн ирмэгийн эхлэлтэй давхцаж, нэгээс олон ирмэг гарахгүй.

Цагаан будаа. 59
Хэрэв чиглэгдсэн графикт G-ээс зам байгаа бол ГЭХДЭЭБ руу, дараа нь буцах ATруу ГЭХДЭЭбайж болохгүй (Зураг 59).
Хэрэв А-аас В хүртэл чиглэсэн зам байвал B гэж хэлнэ хүрэхээж-аас А
38-р зурагт байгаа G баганад В хүрэх боломжтой
А-аас А-д В-ээс хүрэх боломжгүй.
хялбар аргаЧиглүүлсэн график гэдэг нь нэгээс олон оройг агуулаагүй замыг хэлнэ. хаалттай замчиглэсэн график дахь чиглүүлсэн мөчлөг гэж нэрлэдэг.
урт удаан замнь энэ зам дахь ирмэгүүдийн тоо юм.
ЗайА-аас В хүртэлх чиглэлтэй графикийн урт нь А-аас В хүртэлх хамгийн богино замын урт юм. Хэрэв А-аас В хүртэлх зам байхгүй бол А-аас В хүртэлх зайг хязгааргүй гэж нэрлэж, тэмдэглэнэ үү?. А-аас В хүртэлх зайг S (AB) гэж тэмдэглэнэ. 38-р зураг дээрх графикийн хувьд
S (AB) \u003d 1, S (CB) - 2, S (BC) \u003d ?.
Асуудал 9.1.
Далайн эргийн амралтын хотод нэг чиглэлийн хөдөлгөөнийг бий болгосны дараа уулзвар бүрээр орох гудамжны тоо нь түүнээс гарах гудамжны тоотой тэнцдэг болох нь тогтоогджээ. Нэг газраас эхэлж, дуусдаг, гудамжны хэсэг бүрийг яг нэг удаа дайран өнгөрөх эргүүлийн маршрутыг санал болгох боломжтойг нотлох.
Шийдэл.
Хотын хөдөлгөөнийг тодорхойлсон диграф G-г байгуулъя.
Диграф гэж нэрлэдэг холбогдсон,хэрэв тэдгээрийн аль нэг оройгоос бусад нумын дагуу тэдгээрийн чиглэлийг харгалзахгүйгээр явах боломжтой бол. Холбогдсон диграф гэж нэрлэдэг Эйлер,хэрэв Эйлерийн мөчлөгтэй бол.
Теорем 12. Холбогдсон диграф нь түүний орой тус бүрд л байвал Эйлер болноvтэгш байдалг- (v) = г+ (v) .
Теорем нь 4.2-р бодлогын теоремтой яг адилхан батлагдсан.
Бодлогын нөхцлөөс харахад баригдсан G графикийн оройнуудын хувьд d-(v) = d+(v) тэгшитгэл хангагдана. Тиймээс Эйлерийн график G ба Эйлерийн мөчлөг нь хүссэн эргүүлийн замыг тодорхойлно.
Асуудал 9.2.
Хавтгай дээр хязгаарлагдмал тооны цэгүүд тэмдэглэгдсэн байдаг. Зарим хос цэгүүд нь векторуудын эхлэл ба төгсгөл бөгөөд дурын цэг рүү орох векторын тоо нь түүнээс гарах векторуудын тоотой тэнцүү байна. Векторуудын нийлбэрийг ол.
Шийдэл.
Хавтгайн цэгүүд векторуудын хамт диграфыг үүсгэнэ G. Бүх орой нь өөр өөр диграфын мөчлөгийг гэнэ. контур.
Теорем 13. Холбогдсон диграфГЭйлер зөвхөн хэрэв л болГнь хосоороо нийтлэг ирмэггүй контурын нэгдэл юм.
Баталгаа. Хэрэгцээ.G-г Эйлерийн диграф гэж үзье. Түүний дурын оройг авч үзье u1. Зарим нумын дагуу u1 оройг орхиё (u1, u2) Диграф G холбогдсон тул үүнийг хийж болно. d-(u2) = d+(u2) тул нумын дагуу (u2, u3) u2 оройг орхих боломжтой. . G диграф нь хязгаарлагдмал тооны оройтой тул бид өмнө нь байсан ямар нэг w орой дээр ирдэг. Гинжин хэлхээний w цэгээр эхэлж, дуусах хэсэг нь С1 зам юм. G диграфаас C1 контурын нумуудыг хас . Үүссэн диграф G1 (салгасан байж магадгүй) дээр С-д хамаарах оройнуудын орох, гарах зэрэг нэгээр буурч, үлдсэн оройнуудын орох, гарах зэрэг өөрчлөгдөөгүй байна. Иймд С1 диграфын аль ч v оройн хувьд d-(v) = d+(v) тэгшитгэл биелнэ. Тиймээс G1 диграф дээр бид C контурыг ялгаж болно 2 гэх мэт.
Контурыг Эйлерийн мөчлөгт нэгтгэснээр хангалттай байдал нотлогддог (Бодлого 4.2 дахь теоремын баталгааг үзнэ үү).
Теорем нь батлагдсан. Манай бодлогын векторуудыг тодорхойлсон диграф G нь хоорондоо холбоогүй байж магадгүй юм. Батлагдсан теоремыг диграфын холбогдсон хэсэг бүрт хэрэглэснээр бид векторуудыг контур болгон хуваах болно. Нэг контурт хамаарах векторуудын нийлбэр тэгтэй тэнцүү байна. Тиймээс бүх векторуудын нийлбэр тэгтэй тэнцүү байна.

Алгоритмуудыг шууд судалж эхлэхээсээ өмнө графикуудыг компьютерт хэрхэн дүрсэлж байгааг ойлгохын тулд тэдгээрийн талаархи үндсэн мэдлэгтэй байх хэрэгтэй. Энд график онолын бүх талыг нарийвчлан тайлбарлахгүй (үүнийг хийх шаардлагагүй), зөвхөн үл тоомсорлох нь програмчлалын энэ чиглэлийг эзэмшихэд ихээхэн хүндрэл учруулах болно.

Хэд хэдэн жишээ нь графикийн талаар бага зэрэг өнгөц санаа өгөх болно. Тиймээс ердийн график нь метроны газрын зураг эсвэл өөр зам юм. Ялангуяа програмист хүн компьютерийн сүлжээг мэддэг бөгөөд энэ нь мөн график юм. Энд нийтлэг зүйл бол шугамаар холбогдсон цэгүүд байгаа явдал юм. Тиймээс компьютерийн сүлжээнд цэгүүд нь тусдаа серверүүд, шугамууд нь өөр өөр төрлийн цахилгаан дохио юм. Метронд эхнийх нь станцууд, хоёр дахь нь тэдгээрийн хооронд байрлуулсан хонгилууд юм. Графикийн онолд цэгүүдийг нэрлэдэг оргилууд (зангилаа), болон шугамууд хавирга (нумууд). Энэ замаар, графикирмэгээр холбогдсон оройнуудын цуглуулга юм.

Математик нь аливаа зүйлийн агуулгаар бус, харин бүтцээр нь өгөгдсөн бүх зүйлээс хийсвэрлэн авч ажилладаг. Зөвхөн энэ аргыг ашигласнаар бид зарим объектын талаар графиктай адил дүгнэлт хийж болно. Графикийн онол нь математикийн нэг хэсэг учраас зарчмын хувьд объект гэж юу болох нь түүнд огт хамаагүй; Ганц чухал зүйл бол энэ нь график мөн эсэх, өөрөөр хэлбэл графикт шаардлагатай шинж чанаруудтай эсэх юм. Тиймээс, жишээ өгөхийн өмнө бид авч үзэж буй объектод зөвхөн бидний бодлоор аналоги үзүүлэх боломжийг олгодог зүйлийг онцолж, нийтлэг зүйлийг хайж байна.

Компьютерийн сүлжээнд буцаж орцгооё. Энэ нь тодорхой топологитой бөгөөд ердийн байдлаар үүнийг хэд хэдэн компьютер, тэдгээрийг холбосон зам гэж дүрсэлж болно. Доорх зурагт бүрэн торон топологийг жишээ болгон харуулав.

Энэ нь үндсэндээ график юм. Таван компьютер нь оройнууд бөгөөд тэдгээрийн хоорондох холболтууд (дохионы замууд) нь ирмэгүүд юм. Компьютерийг оройгоор сольсноор бид математикийн объектыг олж авдаг - 10 ирмэг, 5 оройтой график. Та оройг дур зоргоороо дугаарлаж болох ба зурагт үзүүлсэн шиг байх албагүй. Энэ жишээнд гогцоо ашиглаагүй, өөрөөр хэлбэл оройг орхиж, тэр даруйд ордог ирмэгийг ашиглаагүй гэдгийг тэмдэглэх нь зүйтэй, гэхдээ гогцоонууд асуудалд тохиолдож болно.

График онолд ашигладаг зарим чухал тэмдэглэгээг энд оруулав.

• G=(V, E), энд G нь график, V нь түүний оройнууд, E нь ирмэгүүд;
• |V| – дараалал (оройнуудын тоо);
• |Э| – графикийн хэмжээ (ирмэгийн тоо).

Манай тохиолдолд (Зураг 1) |V|=5, |E|=10;

Хэрэв аль ч оройгоос өөр орой руу орох боломжтой бол ийм графикийг нэрлэнэ чиг баримжаагүйхолбогдсон график (Зураг 1). График холбогдсон боловч энэ нөхцөл хангагдаагүй бол ийм графикийг нэрлэнэ чиглэсэнэсвэл диграф (Зураг 2).

Чиглүүлсэн ба чиглүүлээгүй график нь оройн зэрэг гэсэн ойлголттой байдаг. Оройн зэрэгбусад оройтой холбох ирмэгүүдийн тоо юм. Графикийн бүх градусын нийлбэр нь түүний бүх ирмэгийн тооноос хоёр дахин их байна. Зураг 2-ын хувьд бүх чадлын нийлбэр нь 20 байна.

Чиглэлгүй графикаас ялгаатай нь диграфт h оройноос s орой руу завсрын оройгүй шилжих боломжтой бөгөөд зөвхөн ирмэг h цэгээс гарч s руу орох үед л шилжих боломжтой ба эсрэгээр биш.

Чиглүүлсэн график нь дараах тэмдэглэгээтэй байна.

G=(V, A), V оройнууд, A нь чиглэсэн ирмэгүүд юм.

Гурав дахь төрлийн графикууд - холимогграфикууд (Зураг 3). Тэдгээр нь чиглүүлсэн болон чиглэлгүй ирмэгүүдтэй байдаг. Албан ёсоор холимог графикийг дараах байдлаар бичнэ: G=(V, E, A), хаалтанд байгаа үсэг бүр нь өмнө нь түүнд хамаарах зүйлийг мөн илэрхийлдэг.

Зураг 3-ын графикт зарим нумыг чиглүүлсэн [(e, a), (e, c), (a, b), (c, a), (d, b)], зарим нь чиглэлгүй [( e, d), (e, b), (d, c)...].

Хоёр ба түүнээс дээш график нь анх харахад бүтцийн хувьд өөр мэт санагдаж болох бөгөөд энэ нь өөр өөр дүрслэлийн улмаас үүсдэг. Гэхдээ энэ нь үргэлж тийм байдаггүй. Хоёр график авъя (Зураг 4).

Эдгээр нь хоорондоо тэнцүү, учир нь нэг графын бүтцийг өөрчлөхгүйгээр өөр нэг график барьж болно. Ийм графикуудыг нэрлэдэг изоморф, өөрөөр хэлбэл, нэг графын тодорхой тооны ирмэгтэй аливаа орой нь нөгөө графикт ижил оройтой байх шинж чанартай байх. Зураг 4-т хоёр изоморф графикийг үзүүлэв.

Графикийн ирмэг бүрд ирмэгийн жин гэж нэрлэгддэг ямар нэг утгыг өгөхөд ийм график үүснэ түдгэлзүүлсэн. Янз бүрийн даалгаварт янз бүрийн хэмжилтүүд нь жингийн үүрэг гүйцэтгэдэг, жишээлбэл, урт, маршрутын үнэ гэх мэт. График дүрслэлд жингийн утгыг ихэвчлэн ирмэгийн хажууд зааж өгдөг.

Бидний авч үзсэн графикуудын аль нэгэнд зам сонгох боломжтой бөгөөд үүнээс гадна нэгээс илүүг сонгох боломжтой. Замнь ирмэгийн тусламжтайгаар дараагийнхтай холбогдсон оройнуудын дараалал юм. Хэрэв эхний болон сүүлчийн оройнууд давхцаж байвал ийм замыг мөчлөг гэж нэрлэдэг. Замын урт нь түүнийг бүрдүүлж буй ирмэгүүдийн тоогоор тодорхойлогддог. Жишээлбэл, Зураг 4.а-д зам нь [(e), (a), (b), (c)] дараалал юм. Энэ зам нь дэд зураас юм, учир нь сүүлийнх нь тодорхойлолт түүнд хамаарна, тухайлбал: G'=(V', E') график нь зөвхөн V' ба E' тохиолдолд G=(V, E) графикийн дэд график болно. В, Е-д харьяалагддаг.