ከልጅነት ጀምሮ ስራውን አስታውሱ - እርሳሱን ከወረቀት ላይ ሳያነሱ እና በሁለቱም በኩል ሁለት ጊዜ ሳያልፉ ክፍት ፖስታ መሳል ያስፈልግዎታል?

ጥቂት አማራጮች አሉ፣ ስለሆነም፣ ከትንሽ ሙከራዎች በኋላ (“2-3-4-2-1-5-4-1st?!”፣ “4-2-1-5-4-3-5 ኛ?! ”) ማንኛውም ልጅ ትክክለኛውን መፍትሔ አግኝቷል። እና ከነጥብ 1 ወይም ከቁጥር 5 ብቻ መሳል መጀመር ያስፈልግዎታል ። ከዚያ በኋላ በማንኛውም አቅጣጫ መንቀሳቀስ በመጨረሻ ለችግሩ መፍትሄ አመጣ።

ስለ እነዚህ ሁለት ነጥቦች, የመጀመሪያው እና አምስተኛው ምንድን ነው? ለስኬታማ መፍትሄ ዋስትና እንዲሆኑ ምን ያስችላቸዋል? ችግሩን ለመፍታት በእያንዳንዱ ነጠላ ነጥቦች ላይ የሚሰበሰቡት “አስፈላጊ” የጎኖች ብዛት፣ ማለትም፣ ያልተለመደ ቁጥር! በእርግጥ, በነጥቦች 1 እና 5 በ 3 ጎኖች, በ 2 እና 4 - በ 4, እና በሁለተኛው - 2. በግራፍ ንድፈ ሃሳብ (ችግሩን በቀላሉ የሚፈታው ይህ ተግሣጽ ነው) ይህ መስፈርት ለ " ክፍት ፖስታ" እንደዚህ ይመስላል

በተገናኘው ግራፍ ውስጥ አንድ ጊዜ ሁሉንም ጫፎቹን የያዘ ፣የመጀመሪያ እና የመጨረሻ ጫፎች የማይገጣጠሙበት መንገድ መፈለግ አስፈላጊ ከሆነ ፣የመጀመሪያ እና የመጨረሻ ጫፎች ጎዶሎ ዲግሪ ያላቸው ብቸኛ ጫፎች መሆን አስፈላጊ እና በቂ ነው።

ይህንን በማወቅ በችግሩ ተመሳሳይ መስፈርቶች ስር "የተዘጋ ኤንቬሎፕ" መሳል እንደማይቻል ግልጽ ይሆናል - ሁሉም ጫፎች ያልተለመደ ዲግሪ አላቸው.

እና በክፍል ጓደኛው ላይ ያለ ማንኛውም ሰው - ምን ደካማ ነው ይላሉ? - በግራፍ ንድፈ ሐሳብ ውስጥ የኋለኛውን ባለማወቅ ላይ ይሰላል!

የግራፍ ቲዎሪ ትልቅ እና በደንብ የተመረመረ መስክ ነው። የተለየ ሂሳብበተጨማሪም ፣ discrete mathematics እንደ የሂሳብ ሎጂክ ፣ የሂሳብ ሳይበርኔቲክስ ፣ የተግባር ሥርዓቶች ንድፈ ሀሳብ እና ወደ 30 የሚጠጉ ተጨማሪ ንድፈ ሀሳቦችን ያዋህዳል።

ግን ወደ ግራፎች ተመለስ። ስለዚህ - በዳርቻዎች የተገናኙ ጫፎች (አንጓዎች) ስብስብ. በጥብቅ ፍቺ፣ ግራፍ የታዘዘ ጥንዶች G=(V፣E) ሲሆን V ባዶ ያልሆነ የርዝመቶች ወይም አንጓዎች ስብስብ ሲሆን ኢ ደግሞ ጠርዞች የሚባሉት ጥንድ ጫፎች ናቸው።

ጫፎች ተጠርተዋል ተርሚናልየጠርዙ ጫፎች (ወይም በቀላሉ ጫፎች) አንድ ጠርዝ በተራው እነዚህን ጫፎች ያገናኛል. የአንድ ጠርዝ ሁለት የጫፍ ጫፎች ጎረቤቶች ይባላሉ.

የጎድን አጥንቶች ሊሆኑ ይችላሉ ተዛማጅ(የጋራ የመጨረሻ ጫፍ አላቸው) እና ብዜቶች(የመጨረሻቸው ጫፎች ስብስቦች ተመሳሳይ ናቸው). የአንዱ ጠርዝ ጫፎች ከተገጣጠሙ, እንዲህ ዓይነቱ ጠርዝ ይባላል ሉፕ.

የቬርቴክስ ዲግሪ(“ክፍት ፖስታውን” አስታውስ?) በእሱ ላይ የተከሰቱትን የጠርዝ ብዛት ይሰይሙ (ማለትም በወርድ ውስጥ የተካተቱ ጠርዞች)። በዚህ ሁኔታ, ቀለበቶች ሁለት ጊዜ ይቆጠራሉ.

የላይኛው ይባላል ተነጥሎየየትኛውም ጠርዝ መጨረሻ ካልሆነ; ማንጠልጠል(ወይም ሉህ) በትክክል የአንድ ጠርዝ ጫፍ ከሆነ.

በግራፍ ቲዎሪ ውስጥ ብቻ እጅግ በጣም ብዙ ትርጓሜዎች አሉ። ግራፉ ሊሆን ይችላል ተኮር(ሁሉም ጠርዞች እንደ ቬክተር ያለ አቅጣጫ አላቸው) ክብደት ያለው(እያንዳንዱ ጠርዝ የተወሰነ ቁጥር ይመደባል, የጠርዙ ክብደት ይባላል), ተገናኝቷል(ማንኛውም ጫፎች፣ ከ ወደ ) እና የመሳሰሉት መንገዶች አሉ። እንደ አንድ ደንብ, በዚህ ጽንሰ-ሐሳብ የተፈቱ የችግሮች መስፋፋት አዳዲስ ትርጓሜዎች እና ጽንሰ-ሐሳቦች እንዲፈጠሩ ምክንያት ሆኗል. ለዚያም ነው ብዙ ትርጓሜዎች እራሳቸው የሚስቡት (በማንኛውም የመማሪያ መጽሐፍ ውስጥ ሊያነቧቸው ይችላሉ), ግን የሚፈቱት ተግባራት ናቸው! ከነሱ መካከል እንደ ክላሲኮች አሉ "የኮኒግስበርግ ሰባት ድልድዮች ችግር"(በግራፍ ቲዎሪ ውስጥ ካሉት የመጀመሪያዎቹ ችግሮች አንዱ በኡለር በ1736 የታተመ) "አራቱ የቀለም ችግር"(እ.ኤ.አ. በ 1852 ተዘጋጅቷል ፣ ግን ማስረጃው የተገኘው በ 1976 ብቻ ነው) "የተጓዥ ሻጭ ችግር", isomorphismይቆጥራል፣ እቅድ ማውጣት

በ"ተጓዥ ሻጭ ችግር" ላይ እናተኩር። አንድ የተለመደ የላብራቶሪ ተግባር በልዩ የሂሳብ ትምህርት እናስብ።

የተጓዥ ሻጩን ችግር ለ() ከተማዎች በ"ስግብግብ ስልተ ቀመር" ይፍቱ። ከተሞች በዘፈቀደ የተመደቡ ናቸው። ችግሩ የተመጣጠነ እንደሆነ አድርገው ይቁጠሩት። የትርፋማነት መስፈርት በከተሞች መካከል ያለው ርቀት ነው. ፕሮግራም ጻፍ።

በመጀመሪያ ደረጃ, ትንሽ ንድፈ ሃሳብ.

ተጓዥ ሻጭ ችግር- በጣም ዝነኛ ከሆኑት ችግሮች አንዱ, ይህም በተጠቀሱት ከተሞች ውስጥ ቢያንስ አንድ ጊዜ በማለፍ በጣም ትርፋማ መንገድ መፈለግ እና ከዚያም ወደ መጀመሪያው ከተማ መመለስን ያካትታል. በችግሩ ሁኔታዎች ውስጥ የመንገዱን ትርፋማነት መስፈርት (አጭሩ ፣ ርካሽ ፣ ድምር መስፈርት ፣ ወዘተ) ይጠቁማል። መንገዱ በእያንዳንዱ ከተማ አንድ ጊዜ ብቻ ማለፍ አለበት (ምርጫው በመካከል ነው ሃሚልቶኒያኛዑደቶች)።

በየከተማው ያለው ተጓዥ ሻጭ እስካሁን ያልጎበኘው የሚቀጥለው ከተማ ምርጫ ስለሚገጥመው ለተመጣጣኝ ተጓዥ ሻጭ ችግር መንገዶች አሉ። ስለዚህ, ለጉዳዮቹ, ተጓዳኝ መስመሮች ቁጥር,,,.

በጣም ኃይለኛ ኮምፒዩተር እንኳን በቀጥታ መቁጠር (ወይም "ብሩት ሃይል") ችግሩን ለመፍታት እንደማይረዳ ግልጽ ነው! ሁኔታው በግምታዊው ስልተ-ቀመር ላይ ያተኮረ መሆኑ በአጋጣሚ አይደለም.

"ስግብግብ አልጎሪዝም" ማለትም "የቅርብ ጎረቤት ዘዴ" ተጓዥ ሻጭን ችግር ለመፍታት በጣም ቀላሉ ዘዴዎች አንዱ ነው. እንደሚከተለው ተዘጋጅቷል፡-

ከተሞች በቅደም ተከተል በመንገዱ ውስጥ ተካተዋል፣ እና እያንዳንዱ ቀጣይ የተካተተው ከተማ በመንገዱ ውስጥ ገና ካልተካተቱት ከሌሎቹ ከመጨረሻው ከተመረጠው ከተማ በጣም ቅርብ መሆን አለበት።

የቃል ስልተ ቀመር እንሥራ።

ተጠቃሚው የከተማዎችን ብዛት ያዘጋጃል - የCITIES_COUNT ቋሚ። በከተሞች መካከል ያለው ርቀት በካሬ ውስጥ ይከማቻል የርቀት ድርድር። እና የከተማ ኢንዴክሶች ትክክለኛ ቅደም ተከተል የሆነው እጅግ በጣም ጥሩው መንገድ በመንገዱ መስመራዊ ድርድር ውስጥ ተከማችቷል።

1. የከተሞች ካርታ የመጀመሪያ ጅምር አለ። ይህንን ለማድረግ, የዘፈቀደ ስልተ ቀመር እንጠቀማለን (የመጀመሪያውን ችግር መስፈርት ማሟላት "ከተሞች በዘፈቀደ ለመወሰን").
2. የተጓዥው ሻጭ መንገድ ይፈለጋል - የ CalcPath አሰራር።
   1. በከተሞች መካከል ያለውን የእርስ በርስ ርቀት ማትሪክስ ያሰላል. -1 በማትሪክስ ውስጥ በሰያፍ መልክ ተከማችቷል ፣ የማትሪክስ የላይኛው ትሪያንግል ይሰላል እና ወደ ታችኛው ይገለበጣል ፣ ምክንያቱም ማትሪክስ ከዋናው ዲያግናል ጋር ተመሳሳይ ነው።
   2. በመቀጠል በሁሉም ከተሞች (iCurr ተለዋዋጭ) ውስጥ "እሮጣለሁ" ከመጀመሪያው (iStart) ጀምሮ, እና ለእያንዳንዳቸው የቅርቡን ከተማ እንፈልጋለን (ርቀቱ አነስተኛ ነው), በ iM ተለዋዋጭ ውስጥ ያስቀምጡት እና ይጨምሩ. ወደ መንገድ መንገድ። በአቅራቢያችን ያለውን ከተማ ስንፈልግ ቀደም ብለን የጎበኘናቸው ከተሞችን ችላ እንላለን (እስከ = -1 ያለውን ርቀት)። በመንገድ ላይ, የመንገዱን አጠቃላይ ርዝመት (ሌን) እንፈልጋለን;
   3. የሚቀጥለውን ከተማ በመንገዱ ላይ ካካተትን በኋላ, ከግምት ውስጥ እንሰርዘዋለን (ከዚህ ከተማ ጋር በተዛመደ አምድ እና ረድፍ ውስጥ -1 በሩቅ ማትሪክስ ውስጥ እናስቀምጣለን).

የዱካ ማፈላለጊያ ገበታ ይህን ይመስላል።

የፕሮግራሙ ውጤት (አውርድ) ለአምስት ከተሞች (ይበልጥ በግልፅ) ከዚህ በታች ቀርቧል።

የመነሻ ከተማ (የሻጩ የትውልድ ከተማ) በቀይ ፣ የተቀረው በሰማያዊ ምልክት ተደርጎበታል ።

መፍትሄው ጉብኝቱ በሚጀምርበት የመነሻ ከተማ ላይ የተመሰረተ መሆኑን ልብ ሊባል ይገባል. ስለዚህ በፕሮግራሙ መጀመሪያ ላይ ተጠቃሚው የመጀመሪያውን (iStart) መምረጥ እንዲችል የሁሉም ከተሞች ዝርዝር ይመሰረታል ። የመነሻ ከተማውን በቀየሩ ቁጥር፣ የተጓዥ ሻጩ መንገድ እንደገና ይሰላል፣ ይህም የሚከተሉትን መፍትሄዎች ይሰጣል።

ሆኖም ግን, የችግሩን መስፈርቶች እናስታውስ. ስለዚህ ለከተሞች 10, 100, 300, መፍትሄዎች እንደሚከተለው ሊሆኑ ይችላሉ.

የተገኙትን መፍትሄዎች ምስላዊ ትንተና በተለይም ለሶስት መቶ ከተሞች (ሻጩ ከመጨረሻው መድረሻ ወደ ትውልድ ቦታው የሚመለስበት ረጅም መንገድ) ፣ “ስግብግብ አልጎሪዝም” ውጤቱን ከሁለት እጥፍ በማይበልጥ ትክክለኛ ትክክለኛ መሆኑን ያረጋግጣል ። መንገድ.. መፍትሄን ለመገምገም ከሂዩሪስቲክ መስፈርቶች ውስጥ አንዱ ደንቡ ነው-በአልጎሪዝም የመጨረሻ ደረጃዎች የተጓዘው መንገድ በመጀመሪያ ደረጃዎች ከተጓዘበት መንገድ ጋር የሚወዳደር ከሆነ ፣ የተገኘው መንገድ በሁኔታዊ ተቀባይነት እንዳለው ሊቆጠር ይችላል ፣ ካልሆነ ፣ የበለጠ ጥሩ መፍትሄዎች። ሊኖር ይችላል።

የታሰበው ስልተ ቀመር ነው። ሂዩሪስቲክ. በአብዛኛዎቹ የሂዩሪስቲክ ዘዴዎች (ዘዴ ዝቅተኛው የተዘረጋ ዛፍ, አስመስሎ የማጥቂያ ዘዴ, ዘዴ ቅርንጫፎች እና ድንበሮች) በጣም ቀልጣፋ መንገድ ሳይሆን ግምታዊ መፍትሄ ነው። በተግባር, ለችግሩ ግምታዊ, መፍትሄ ለማግኘት ይህ ብቸኛው መንገድ ነው. እርግጥ ነው, ጥሩው መንገድ ሙሉ ለሙሉ ብቻ ሊሰጥ ይችላል አማራጮችን መቁጠርነገር ግን የእነዚህ አማራጮች ቁጥር ባለ 156 አሃዝ ቁጥር ለተገለጸባቸው ቢያንስ ለ 100 ከተሞች ይህን ማድረግ እውነት ነውን?!

ስነ ጽሑፍ

1. Aho A., Hopcroft J., Ulman J. Data Structures and Algorithms. - ኤም.: ዊሊያምስ ማተሚያ ቤት, 2001.
2. ቦንዳሬቭ ቪ.ኤም., Rublinetsky V.I., Kachko E.G. የፕሮግራም አወጣጥ መሰረታዊ ነገሮች. - ካርኪቭ፡ ፎሊዮ; ሮስቶቭ n / አንድ: ፊኒክስ, 1997.
3. Kormen T., Leyzerson Ch., Rivest R. Algorithms: ግንባታ እና ትንተና. - ኤም.: MTsNMO, 2001.
4. ሮማኖቭስኪ I.V. የተለየ ትንተና… - 2 ኛ እትም፣ ተሻሽሏል። - ሴንት ፒተርስበርግ: ኔቪስኪ ቀበሌኛ, 2000.
5. Shen A. Programming: theorems and problem - ኤም.: MTsNMO, 1995.

ለማዘዝ የልዩ ሂሳብ መፍትሄ

ማንኛውም ጥያቄ ካለዎት - በአስተያየቶቹ ውስጥ ይጠይቁ. ችግሮችን መፍታት ያስፈልጋል - ማዘዝ.
እርስዎን ለመርዳት ደስተኞች ነን!

ግራፊክስ

ግራፍ የመነጨው በአስራ ስምንተኛው ክፍለ ዘመን ታዋቂው የሂሳብ ሊቅ ሊዮናርድ ኡለር አሁን ያለውን የክላሲካል የኮኒግስበርግ ድልድይ ችግር ለመፍታት ሲሞክር ነው። በዚ ግዜ’ዚ ኣብ ከተማ ኮይንስበርግ በለስ ላይ እንደሚታየው በሰባት ድልድዮች ከፕሪጎል ወንዝ ዳርቻ እና እርስ በርስ የተያያዙ ሁለት ደሴቶች ነበሩ. 7.1. ተግባሩ እንደሚከተለው ነው-በእያንዳንዱ ድልድይ ላይ በትክክል አንድ ጊዜ ካለፉ በኋላ በእግር ጉዞው ወደ ተጀመረበት ቦታ እንዲመለሱ በከተማው ዙሪያ በእግር ለመጓዝ። ይህንን ችግር ለመፍታት ኤዩለር ኮኒግስበርግን እንደ ግራፍ አሳይቷል ፣ ቁመቶቹን ከከተማው ክፍሎች ጋር ፣ እና ጫፎቹን እነዚህን ክፍሎች በሚያገናኙ ድልድዮች ለይቷል። በ § 7.1 እንደምናሳየው ኡለር በከተማው ዙሪያ የሚፈለገው መንገድ አለመኖሩን በማረጋገጥ ተሳክቶለታል።

ምስል 7.1. የድሮ ኮኒግስበርግ እቅድ

በዚህ ምእራፍ፣ በግራፍ ቲዎሪ ውስጥ ጥቅም ላይ የዋለውን መደበኛ የቃላት አነጋገር እናስተዋውቃለን እና ግራፎች ሊፈቱዋቸው የሚችሏቸውን በርካታ ልዩ ችግሮችን እንወያይበታለን። በተለይም ዛፎች ከሚባሉት የግራፍ ክፍል ጋር እንተዋወቃለን. ዛፎች በተዋረድ ሥርዓት ውስጥ የተደራጁ መረጃዎችን የሚወክሉ የተፈጥሮ ሞዴል ናቸው። ነጠላ እቃዎችን ለመለየት በዛፍ ውስጥ መፈለግ እና በዛፍ ውስጥ ያሉ መረጃዎችን መደርደር በኮምፒተር ሳይንስ ውስጥ ጠቃሚ የጥረት ነጥቦች ናቸው። በዚህ ምዕራፍ አባሪ ላይ በዛፎች የተደራጁ መረጃዎችን መደርደር እና መፈለግን እንመለከታለን።

ግራፎች እና ቃላት

በለስ ላይ. 7.1 የኮኒግስበርግ ሰባት ድልድዮችን እንደሚከተለው ያሳያል። በአሥራ ስምንተኛው ክፍለ ዘመን እንዴት እንደተደረደሩ. በኡለር የተመለከተው ችግር በእያንዳንዱ ድልድይ ላይ በትክክል አንድ ጊዜ የሚያልፍ እና በከተማው ውስጥ በተመሳሳይ ቦታ የሚጀምር እና የሚያበቃ የእግር መንገድ ማግኘት ይቻል ይሆን?

የተግባር ሞዴል ነው። ግራፍ፣ብዙ ያቀፈ ጫፎችእና ብዙ የጎድን አጥንት፣የማገናኘት ጫፎች. ጫፎች A፣ B፣ C እና ዲ የወንዙን ​​እና የደሴቱን ዳርቻዎች እና የጎድን አጥንቶችን ያመለክታሉ ሀ፣ ሐ, ሐ,መረ እና ሰሰባት ድልድዮችን ይወክላሉ (ምስል 7.2 ይመልከቱ)። የሚፈለገው መንገድ (ካለ) እያንዳንዳቸው አንድ ጊዜ ብቻ እንዲዘዋወሩ በሚያስችል መንገድ የግራፉን ጠርዞች ከማለፍ ጋር ይዛመዳል. የጎድን አጥንቱ ማለፊያ በግልጽ ከወንዙ መሻገሪያ ድልድይ ጋር ይዛመዳል።

ምስል 7.2. የኮኒግስበርግ ድልድይ ችግር ሞዴል

መሄጃ ያለበት ግራፍ በአንድ ጫፍ የሚጀምር እና የሚያልቅ እና በግራፉ ጠርዞች ላይ በትክክል አንድ ጊዜ የሚያልፍበት መንገድ አለ syler ግራፍ.የሚፈለገው መንገድ የሚያልፍበት የጫፍ ቅደም ተከተል (ምናልባትም ከድግግሞሽ ጋር) እንዲሁም መንገዱ ራሱ ይባላል። ኡለር ዑደት. ዩለር በግራፍ ውስጥ የዩለር ዑደት ካለ ፣ ወደ አንዳንድ ወርድ የሚያመራው እያንዳንዱ ጠርዝ ፣ ከዚህ ወርድ 1 ሌላ ጠርዝ መኖር እንዳለበት አስተውሏል ፣ እና ከዚህ ቀላል ምልከታ የሚከተለው መደምደሚያ አግኝቷል-የዩለር ዑደት ካለ በዚህ ግራፍ ውስጥ, ከዚያም እኩል የሆኑ ጠርዞች ወደ እያንዳንዱ ጫፍ መቅረብ አለባቸው.

በተጨማሪም፣ ኡለር ተቃራኒውን ማረጋገጫ በማረጋገጥ ተሳክቶለታል፣ ስለዚህም ማንኛውም ጥንድ ጫፎች በተወሰኑ ቅደም ተከተሎች የተገናኙበት ግራፍ ሁሉም ጫፎች እኩል ዲግሪ ካላቸው ብቻ ነው Euler ነው። ዲግሪጫፎች v ቁጥር δ(v) ተብሎ ይጠራል የጎድን አጥንት, እሷ ድንገተኛ 2 .

የኮኒግስበርግ ድልድይ ችግርን በሚመስል ግራፍ ላይ የዩለር ዑደት እንደማይገኝ አሁን ግልፅ ነው። በእርግጥ የሁሉም ጫፎች ደረጃዎች እንግዳ ናቸው፡- δ(ለ) = δ(ሐ)= δ (D) = 3 እና δ(ሀ) = 5. በኡለር እርዳታ የድልድዩን ችግር ሲፈታ እንዳጠናናቸው ግራፎች ብዙ ተግባራዊ ችግሮችን ለመፍታት ጥቅም ላይ መዋል የጀመሩ ሲሆን ጥናታቸውም ትልቅ የሒሳብ ክፍል ሆነ።

ቀላል ግራፍእንደ ጥንድ G = (V፣ ኢ)የት V አንድ ውሱን ጫፎች ስብስብ ነው, እና ኢየተወሰነ የጠርዝ ስብስብ ነው፣ እና ሊይዝ አይችልም። ቀለበቶች(በተመሳሳይ ጫፍ የሚጀምሩ እና የሚጨርሱ ጠርዞች) እና በርካታ ጠርዞች(ብዙዎቹ ተመሳሳይ ጥንድ ጫፎችን የሚያገናኙ ብዙ ጠርዞች ናቸው)። በስእል ላይ የሚታየው ግራፍ. 7.2. ቀላል አይደለም ምክንያቱም ለምሳሌ, ጫፎች ግንእና አትበሁለት ጠርዞች የተገናኙ ናቸው (እነዚህ ጠርዞች ብቻ ብዙ ይባላሉ).

ሁለት ጫፎች ዩ እና ቁበቀላል ግራፍ ተጠርተዋል ተዛማጅበተወሰነ ጠርዝ ከተገናኙ ሠነው የተባለው በአጋጣሚከላይ u (እና v ). ስለዚህ, አንድ ስብስብ መገመት እንችላለን ኢጠርዞቹን እንደ ጥንዶች የተጠጋ ጫፎች ስብስብ ነው፣ ስለዚህም በስብስቡ ላይ የማይለዋወጥ፣ የተመጣጠነ ግንኙነትን ይገልፃል። ቁ.የመተጣጠፍ ችሎታ አለመኖር በቀላል ግራፍ ውስጥ ምንም ቀለበቶች የሉም ፣ ማለትም ፣ ሁለቱም ጫፎች በተመሳሳይ ደረጃ ላይ ይገኛሉ። የግንኙነቱ ተምሳሌት ከጫፍ እውነታ ይከተላል ሠጠርዙን በማገናኘት ላይ እናከ ቪ፣ያገናኛል እና ቁከ እና(በሌላ አነጋገር, ጠርዞቹ አቅጣጫዊ አይደሉም, ማለትም, ምንም አቅጣጫ የላቸውም). ጥንድ ጫፎችን የሚያገናኝ የቀላል ግራፍ ብቸኛው ጠርዝ ዩ እና ቪ፣ብለን እንጠቁማለን። እና ቁ(ወይም ቪ)

በግራፍ ጫፎች ስብስብ ላይ ያለው የግንኙነት አመክንዮአዊ ማትሪክስ ፣ በጠርዙ የተሰጠው ፣ ይባላል። , የአጎራባች ማትሪክስ.የግንኙነቱ ተምሳሌት ከአጎራባች ማትሪክስ M አንጻር ሲታይ ኤም ስለ ዋናው ሰያፍ የተመጣጠነ። እና በማትሪክስ ኤም ዋና ዲያግናል ላይ ያለው የዚህ ግንኙነት ተለዋዋጭነት ባለመኖሩ "ኤል" ማለት ነው.

ምሳሌ 7.1. ግራፍ ይሳሉ G(V፣ E) ከቁመቶች ስብስብ ጋር V = (a, b, c, d, e) እና የጠርዝ ስብስብ ኢ = (ab, ae, bc, bd, ce, de). የአጎራባች ማትሪክስ ይፃፉ።

ውሳኔ. ግራፍ G በ fig. 7.3.

ምስል 7.3.

የእሱ ተጓዳኝ ማትሪክስ የሚከተለው ነው-

ግራፉን ወደነበረበት ለመመለስ፣ ከዋናው ዲያግናል በላይ የሆኑትን የአጃቢ ማትሪክስ አባሎችን ብቻ እንፈልጋለን።

ንዑስ አንቀጽግራፍ G = (V, E) በግራፍ G' = (V', E') ውስጥ E'C E እና V'C V ይባላል.

ምሳሌ 7.2በስእል ላይ ከሚታዩት ኤች፣ ኬ እና ኤል ግራፎች መካከል ይፈልጉ። 7.4፣ የግራፍ ጂ ንዑስ ግራፎች።

ውሳኔ.በስእል ላይ እንደሚታየው የግራፎቹን ጫፎች G, H እና K ያመልክቱ. 7.5. ግራፍዎቹ H እና K የጂ ንዑስ ግራፎች ናቸው፣ ከጽሁፎቻችን መረዳት እንደሚቻለው። ግራፉ L የጂ ንዑስ ግራፍ አይደለም፣ ምክንያቱም ኢንዴክስ 4 ወርድ ስላለው፣ G ግን የለውም።

መንገድርዝመት ክ በግራፍ G ውስጥ እንደዚህ ያለ የቁመቶች ቅደም ተከተል ይባላል ቁ 0 , ቁ 1 , …, ቁ ክ , ለእያንዳንዱ i = 1, ..., k ጥንድ ቁ እኔ – 1 ቁ እኔ የግራፉን ጠርዝ ይመሰርታል. እኛ እንደዚህ ያለ መንገድ እንሰይማለን ቁ 0 ቁ 1 … ቁ ክ . ለምሳሌ፣ 1 4 3 2 5 የርዝመት መንገድ ነው 4 በአምድ G ከምሳሌ 7.2።

ጂ ኤች

ኬ ኤል

ምስል 7.4.

ዑደትበግራፍ ውስጥ የቋሚዎች ቅደም ተከተል ይባላል ቁ 0 , ቁ 1 , … , ቁ ክ , እያንዳንዳቸው ጥንድ የአንድ ጠርዝ ጫፎች ናቸው, እና ቁ 0 = ቁ 1 , እና የተቀሩት ጫፎች (እና ጠርዞች) አይደገሙም. በሌላ አገላለጽ ዑደት ማለት በእያንዳንዱ ጫፎቹ እና ጫፎቹ አንድ ጊዜ ብቻ የሚያልፍ የተዘጋ መንገድ ነው።

1 2 1 2 3

ምስል 7.5

ምሳሌ 7.3.ዑደቶችን በግራፍ G ከምሳሌ 7.2 ይፈልጉ።

ውሳኔ.በዚህ ግራፍ ውስጥ ሁለት የተለያዩ የርዝመት 5 ዑደቶች አሉ።

1 3 2 5 4 1 እና 1 2 5 4 3 1

በዘፈቀደ የዑደቱ ጫፍ በመነሳት እነዚህን ዑደቶች በአንድ አቅጣጫ እና በሌላ አቅጣጫ ማለፍ እንችላለን። በተጨማሪም፣ በግራፉ ውስጥ ሦስት የተለያዩ የርዝመት 4 ዑደቶች አሉ።

1 2 5 4 1, 1 2 3 4 1 and 2 5 4 3 2,

እና ሁለት ርዝመት ያላቸው ቀለበቶች 3:

1 2 3 1 እና 1 3 4 1.

ዑደቶች የሌሉበት ግራፍ ይባላል አሲኪሊክበኮምፒዩተር ውስጥ የሚነሱ የዛፍ አወቃቀሮች ልዩ የአሲክሊክ ግራፎች ናቸው. በኋላ በዚህ ምዕራፍ ውስጥ እንነጋገራለን.

Earl, ይባላል የተገናኘ፣የትኛውም ጥንድ ጫፎች በተወሰነ መንገድ ከተገናኙ። ማንኛውም አጠቃላይ ግራፍ ወደ ንዑስ ግራፎች ሊከፋፈል ይችላል, እያንዳንዱም ተያያዥነት ያለው ሆኖ ይወጣል. እንደነዚህ ያሉ የተገናኙ አካላት ዝቅተኛው ቁጥር ይባላል የግንኙነት ቁጥርግራፍ እና በ ይገለጻል ሐ(ጂ) . የግንኙነቶች ጉዳዮች በግራፍ ቲዎሪ ወደ ኮምፒውተር ኔትወርኮች ትግበራዎች ትልቅ ጠቀሜታ አላቸው። የሚከተለው ስልተ ቀመር የአንድን ግራፍ የግንኙነት ቁጥር ለመወሰን ይጠቅማል።

የግንኙነት ስልተ ቀመር.

G = (V፣ E) ግራፍ ይሁን። አልጎሪዝም እሴቱን ለማስላት የተነደፈ ነው። ሐ = ሐ(ጂ), እነዚያ። የተሰጠው ግራፍ G የተገናኙ አካላት ብዛት.

ወ፡=V;

እያለቪ ≠ øመ ስ ራ ት

ይምረጡ y Є ቪ’

ከ y ጋር በመንገድ የሚገናኙትን ጫፎች ያግኙ;

ሽፋኑን ከ ላይ ያስወግዱቪ' እና

ተጓዳኝ ጠርዞች ከ E;

ሐ:= ሐ+1;

ምሳሌ 7.4.በምስል ላይ በሚታየው ግራፍ ላይ የግንኙነት ስልተ ቀመር ሥራን ተከተል. 7.6.

ምስል 7.6.

ውሳኔ.ሰንጠረዥ ይመልከቱ. 7.1.

ሠንጠረዥ 7.1.

የመጀመሪያ እሴቶች	{1,2,3,4,5,6,7,8}
ምርጫ y = 1
ምርጫ y = 2
ምርጫ y = 7

ስለዚህ፣ ሐ(ጂ) = 3. ተዛማጅ የግንኙነት ክፍሎች በምስል ውስጥ ይታያሉ. 7.7.

5

የከፍተኛ ሙያዊ ትምህርት የፌዴራል ግዛት የትምህርት ተቋም

"የሞርዶቪያ ግዛት ፔዳጎጂካል ተቋም በኤም.ኢ. ኤቭሴቪቫ"

የፊዚክስ እና የሂሳብ ፋኩልቲ

ረቂቅ

በዚህ ርዕስ ላይ፡-

"የግራፍ ቲዎሪ"

ተፈጸመ፡ ተማሪ

ቡድን MDM-109

ዶብሪንኪና ኦ.ኤ.

የተረጋገጠው በ: Lapina I.E.

ሳራንስክ 2014

መግቢያ …………………………………………………………………………………. 3

1. የግራፍ ቲዎሪ መሰረታዊ ፅንሰ-ሀሳቦች ………………………………………………………… 4

2. የግራፎች ምሳሌዎች …………………………………………………………………………………………. 8

3. የኡለር ግራፎች ………………………………………………………………………………… 13

4. የግራፍ ቲዎሪ አፕሊኬሽኖች ምሳሌዎች …………………………………………………. 16

5. የአጭሩ መንገድ ችግር ………………………………………………………………………… 18

6. ከፍተኛውን ፍሰት ለማግኘት አልጎሪዝም ………………………………………… 27

ማጠቃለያ ………………………………………………………………………………………………… 38

ዋቢዎች ………………………………………………………………………………………… 39

መግቢያ

ከቅርብ ጊዜ ወዲህ፣ ወደ ተለያዩ የሳይንስና ቴክኖሎጂ ቅርንጫፎች የማያቋርጥ የሒሳብ ዘዴዎች እየገቡ ነው። የሂሳብ አሰራር ሂደት የኢኮኖሚ ሳይንስንም ነካ።

የግራፍ ጽንሰ-ሐሳብ በራሱ በጣም ቀላል, በሳይንስ ውስጥ በጣም ፍሬያማ ሆኖ ተገኝቷል እናም ብዙ ጊዜ ጥቅም ላይ ይውላል. የግራፍ ቲዎሪ ግራፎችን እንደ ረቂቅ የሂሳብ አቀማመጦች ያጠናል፣ ልዩ ትርጉማቸው ምንም ይሁን ምን፣ የተገኘው አጠቃላይ ውጤት በተለያዩ ዘርፎች ላይ ይተገበራል።

"ቆጠራ" የሚለው ቃል የዜግነት መብትን አግኝቷል እና በ 1936 ወደ ሂሳብ ቋንቋ የገባው የኮኒግ ሞኖግራፍ ከታተመ በኋላ. ይዘታቸው ምንም ይሁን ምን ለመጀመሪያ ጊዜ ግራፎች እንደ ገለልተኛ የሒሳብ ዕቃዎች ይማራሉ ።

የግራፎች ጥናት ዛሬ ጠቃሚ ነው. በጣም አጭሩ ተዘዋዋሪ ወይም በአቅራቢያው የሚገኘውን የግሮሰሪ መደብር መፈለግ ፣ ጥሩውን መንገድ ማቀድ - እነዚህ ሁሉ የዕለት ተዕለት ሕይወታችን ምሳሌዎች ናቸው። እነዚህ እና ሌሎች በርካታ ችግሮች ግራፎችን በመጠቀም መፍታት ይቻላል.

በዚህ ጽሑፍ ውስጥ በርካታ መሠረታዊ ጽንሰ-ሐሳቦች ተዘርዝረዋል, የግራፍ ንድፈ ሃሳብ አተገባበር ምሳሌዎችም ተሰጥተዋል እና በግራፍ ንድፈ ሃሳብ ላይ የተመሰረቱ ኢኮኖሚያዊ ችግሮችን ለመፍታት ሁለት አቀራረቦች ተወስደዋል.

1. የግራፍ ንድፈ ሐሳብ መሰረታዊ ጽንሰ-ሐሳቦች

ግራፍ በማስተዋል እንደ የክበቦች ስብስብ እና እነሱን የሚያገናኙ የመስመሮች ስብስብ ተደርጎ ሊወሰድ የሚችል ስርዓት ነው (ምስል 1)።

ክበቦች የግራፍ ጫፎች ይባላሉ, ቀስቶች ያሏቸው መስመሮች ቀስቶች ይባላሉ, እና ቀስቶች የሌላቸው መስመሮች ጠርዝ ይባላሉ. የመስመሮቹ አቅጣጫ የማይለይበት ግራፍ (ሁሉም መስመሮች ጠርዝ ናቸው) ያልተስተካከለ (ምስል 1, A) ይባላል; የመስመሮቹ አቅጣጫ መሰረታዊ የሆነበት ግራፍ (መስመሮቹ አርከስ ናቸው) ተኮር (ምስል 1, B) ይባላል.

ዲፍ 1. የተወሰነ ስብስብ ተሰጥቷል X፣ ያቀፈ nንጥረ ነገሮች ( X={1፣ 2፣…፣ n)) ፣ የግራፉ ጫፎች ፣ እና የካርቴዥያ ምርት X ×X ንዑስ ክፍል V ፣ ማለትም ፣ ማለትም።
, የ arcs ስብስብ ይባላል, ከዚያም የሚመራው ግራፍ G ስብስብ (X, V) ነው.

ዲፍ 2. ያልተመራ ግራፍ የ X ስብስብ እና ያልተስተካከሉ ጥንድ ንጥረ ነገሮች ስብስብ ነው, እያንዳንዱም የ X ነው.

በ i እና j ጫፎች መካከል ያለ ቅስት ፣
, (i, j) እንጠቁማለን. የግራፍ ቅስቶች ብዛት በ m (V = () ይገለጻል
)).

ዲፍ 3. ንኡስ ግራፍ በዚህ ስብስብ ውስጥ የሚገኙትን ጫፎች (አርክስ) የሚያገናኙት ጫፎች በአንድ ላይ በንዑስ ስብስብ የተፈጠረ የግራፍ አካል ነው። አንዳንድ ጠርዞችን (አርክን) ከግራፉ ላይ ካስወገድን, ከፊል ግራፍ እናገኛለን.

ዲፍ 4. ሁለት ጫፎች በጠርዝ (አርክ) ከተገናኙ በአጠገብ ይባላሉ. የተጎራባች ጫፎች የተዛማጁ ጠርዝ (አርክ) የድንበር ጫፎች ይባላሉ, እና ይህ ጠርዝ (አርክ) ወደ ተጓዳኝ ጫፎች ክስተት ይባላል.

Def.5. ዱካ የአርከስ ቅደም ተከተል ነው (በሚመራው ግራፍ) የአንድ ቅስት መጨረሻ የሌላ ቅስት መጀመሪያ ነው።

ዲፍ 5.1. ቀላል መንገድ ምንም ቅስት ሁለት ጊዜ የማይከሰትበት መንገድ ነው.

ዲፍ 5.2. ኤለመንታሪ ዱካ ምንም አይነት ወርድ ሁለት ጊዜ የማይከሰትበት መንገድ ነው።

ዲፍ 5.3. ዱካ የጫፍ ጫፍ ከመነሻው ጫፍ ጋር ተመሳሳይ የሆነ መንገድ ነው.

ዲፍ 5.4 የመንገዱን ርዝመት (ኮንቱር) የመንገዱን ቅስቶች ቁጥር (ወይም የአርከቦቹ ርዝመቶች ድምር, የኋለኛው ከተሰጠ).

Def.6. ከ (i፣ j) ያለው ግራፍ ቪ ይከተላል (j, i) ቪ ሲሜትሪክ ይባላል።

ዲፍ 7. ከ (i, j) ከሆነ. ቪ የሚያመለክተው (j, i)
ቪ, ከዚያ ተጓዳኝ ግራፍ አንቲሲሜትሪክ ይባላል.

ዲፍ 8.1. ሰንሰለት የአንድ ጠርዝ መጨረሻ (በዚያ ዝግጅት) የሌላው መጀመሪያ እንዲሆን ሊደረደር የሚችል የጠርዝ ስብስብ ነው (በማይመራው ግራፍ)።

ዲፍ 8.2. ሰንሰለት የተጠጋ ጫፎች ቅደም ተከተል ነው.

ዲፍ 9. የተዘጋ ዑደት ዑደት ይባላል.

ዲፍ 10.1. በሁሉም የግራፍ ጫፎች ውስጥ የሚያልፈው ኤሌሜንታሪ ሰንሰለት (ዑደት፣ ዱካ፣ ኮንቱር) የሃሚልቶኒያ ሰንሰለት (በቅደም ተከተል፣ ዑደት፣ መንገድ፣ ኮንቱር) ይባላል።

ዲፍ 10.2. የግራፉን ሁሉንም ጠርዞች (አርክሶች) የያዘ ቀላል ሰንሰለት (ዑደት ፣ መንገድ ፣ ኮንቱር) ኢዩለር ሰንሰለት ይባላል (በቅደም ተከተል ፣ ዑደት ፣ መንገድ ፣ ኮንቱር)።

ዲፍ 11. የግራፍ ሁለት ጫፎች በሰንሰለት ሊገናኙ የሚችሉ ከሆነ, ግራፉ ተያያዥ ይባላል. ግራፉ ካልተገናኘ, ከዚያም ወደ ተያያዥ ንዑስ ክፍሎች ሊከፋፈል ይችላል, ክፍሎች ይባላሉ.

ዲፍ 12. የግራፍ ተያያዥነት ዝቅተኛው የጠርዝ ብዛት ነው, ከተወገደ በኋላ ግራፉ ይቋረጣል. ለተመሩ ግራፎች፣ የግራፉ ሁለት ጫፎች በአንድ መንገድ ሊገናኙ የሚችሉ ከሆነ፣ ግራፉ በጥብቅ የተገናኘ ነው ተብሏል። የዩለር ዑደት ያለው የተገናኘ ግራፍ ኢዩለር ግራፍ ይባላል።

ዲፍ 13. በማይመራው ግራፍ ውስጥ, የቬርቴክስ ዲግሪ i ቁጥር ነው በእሱ ላይ ክስተት ጠርዞች. ግልጽ ነው፣
. የሁሉም ጫፎች ዲግሪዎች ከ n - 1 ጋር እኩል የሆነ ግራፍ ሙሉ ይባላል። የወርድ ዲግሪው ሁሉም እኩል የሆነ ግራፍ ተመሳሳይነት ይባላል።

ዲፍ 14. በእሱ ላይ ምንም የጠርዝ ክስተት የሌለበት ጫፍ (እ.ኤ.አ.) = 0) ተነጥሎ ይባላል። በእሱ ላይ አንድ የጠርዝ ክስተት ብቻ የሆነበት ጫፍ ( = 1) ተንጠልጥሎ ይባላል።

ዲፍ 15. የግራፉን ተጓዳኝ ማትሪክስ እንደ n × n ካሬ ማትሪክስ ፣ ኤለመንት ይግለጹ አንድ ከሆነ (i, j) ጋር እኩል ነው. V፣ እና ዜሮ ከሆነ (i፣ j)
ቪ፣አይ፣ጄ X. ላልተመራ ግራፍ፣ የአጎራባች ማትሪክስ ሁል ጊዜ የተመጣጠነ ነው።

ዲፍ 16. ለግራፍ ጠርዞች የአደጋ ማትሪክስ እንደ አራት ማዕዘን ቅርጽ ያለው ማትሪክስ n × m, ኤለመንት እንገልጻለን. ይህም ከአንዱ ጋር እኩል ነው ቬርቴክስ i በጠርዝ j ላይ ከተከሰተ እና ዜሮ ካልሆነ i = 1, n, j = 1, m.

ዲፍ 17. የግራፍ አርከስ ክስተት ማትሪክስ አራት ማዕዘን ቅርጽ ያለው ማትሪክስ m x n ነው፣ የሪጅ ኤለመንት ከፕላስ አንድ ጋር እኩል ነው፣ ቅስት ከሆነ ከ vertex i ይመጣል፣ ከአንዱ ሲቀነስ፣ ቅስት ከሆነ ወደ vertex i ያስገባል, እና በሌሎች ሁኔታዎች ዜሮ, i = 1, n, j = 1, m

ዲፍ 18. ዛፍ ቀላል ዑደት የሌለበት እና ቢያንስ ሁለት ጫፎች ያሉት የተገናኘ ግራፍ ነው. ለአንድ ዛፍ m = n - 1, እና የተንጠለጠሉ ጫፎች ቁጥር ነው
በዛፍ ላይ ያሉ ሁለት ጫፎች በአንድ መንገድ የተገናኙ መሆናቸውን ለማሳየት ቀላል ነው.

ዲፍ 19. የቅድመ አያት ዛፍ ቀጥተኛ ዛፍ ነው, ከሥሩ ሥር ተብሎ የሚጠራው አንዱ ጫፎች ምንም የሚመጡ ቅስቶች የሉትም, እና የቀሪዎቹ ጫፎች የማዘንበል ደረጃዎች ከአንድ ጋር እኩል ናቸው.

ዲፍ 20. ፕላላር (ፕላላር) በአውሮፕላን ላይ የሚቀረጽ ግራፍ ሲሆን የተለያዩ ክበቦች ከተለያዩ ጫፎች ጋር በሚዛመዱበት መንገድ እና ምንም ሁለት ጠርዞች ከድንበራቸው ውጭ የጋራ ነጥቦች የላቸውም (አይገናኙም)። ለዕቅድ ግራፍ፣ የፊት ፅንሰ-ሀሳብ አለ - የአውሮፕላኑ ክፍል በጠርዝ የታሰረ እና በውስጡም ጫፎችም ሆነ ጠርዞች የለውም።

ዲፍ 21. የፊት ደረጃው የድንበሩ ጠርዝ ቁጥር ነው (የተንጠለጠሉ ጠርዞች ሁለት ጊዜ ይቆጠራሉ).

ማንኛውም የተገናኘ የአውሮፕላን ግራፍ G ከድርብ የተገናኘ የአውሮፕላን ግራፍ G * ጋር ሊዛመድ ይችላል፣ እንደሚከተለው ይገለጻል፡ እያንዳንዱ የግራፍ G ፊት ከግራፉ G * እያንዳንዱ ጠርዝ V ጋር ይዛመዳል ፣ ይህም ለ ወሰን ነው። ፊቶች z1 እና z2፣ ከግራፉ G * ጠርዝ V * ጋር ይዛመዳል ከ z1 እና z2 ጋር የሚዛመዱትን ጫፎች ያገናኛል።

2. የግራፎች ምሳሌዎች

ሙሉ በሙሉ የተቆራረጡ ግራፎች . የጠርዝ ስብስብ ባዶ የሆነ ግራፍ ይባላል በጣም የማይጣጣም(ወይም ባዶ) ግራፍ.ሙሉ በሙሉ የተቋረጠ ግራፍ ከ n ጫፎች ጋር በ N n እናሳያለን; ቁጥር 4 በስእል ውስጥ ይታያል. 1. ልብ ይበሉ በሙሉ በሙሉ የተቋረጠ ግራፍ ፣ ሁሉም ጫፎች የተገለሉ ናቸው። ሙሉ በሙሉ የተቆራረጡ ግራፎች ብዙም ፍላጎት የላቸውም።

የተሟሉ ግራፎች . ማንኛውም ሁለት ጫፎች አጠገብ ያሉበት ቀላል ግራፍ ይባላል የተሟላ ግራፍ.የተሟላ ግራፍ ከ n ጫፎች ጋር ብዙውን ጊዜ የሚገለጸው በ . ይቆጥራል። እና በለስ ላይ ይታያል. 2 እና 3. በትክክል n (n - 1) / 2 ጠርዞች አሉት.

መደበኛ ግራፎች . ሁሉም ጫፎች ተመሳሳይ ዲግሪ ያላቸው ግራፍ ይባላል መደበኛ ግራፍ.የእያንዳንዱ ጫፍ ደረጃ r ከሆነ, ከዚያም ግራፉ ይባላል መደበኛ ዲግሪአር . የዲግሪ 3 መደበኛ ግራፎች, እንዲሁም ይባላል ኪዩቢክ(ወይም ትራይቫለንት)ግራፎች (ለምሳሌ, ምስል 2 እና 4 ይመልከቱ). ሌላው በጣም የታወቀ የኩቢክ ግራፍ ምሳሌ ተብሎ የሚጠራው ነው ፒተርሰን ቆጠራበለስ ላይ ይታያል. 5. እያንዳንዱ ሙሉ በሙሉ የተቋረጠ ግራፍ መደበኛ ዲግሪ 0 መሆኑን እና እያንዳንዱ ሙሉ ግራፍ K n የዲግሪ n - 1 መደበኛ መሆኑን ልብ ይበሉ።

የፕላቶኒክ ግራፎች . ከመደበኛ ግራፎች መካከል የፕላቶኒክ ግራፎች የሚባሉት በተለይ ትኩረት የሚስቡ ናቸው - በግራፎች እና በአምስት መደበኛ የ polyhedra ጠርዞች የተሰሩ ግራፎች - የፕላቶኒክ ጠጣር-ቴትራሄድሮን ፣ ኩብ ፣ ኦክታድሮን ፣ ዶዲካሄድሮን እና ኢኮሳሄድሮን። ግራፍ ከ tetrahedron (ምስል 2) ጋር ይዛመዳል; ከኩብ እና ከ octahedron ጋር የሚዛመዱ ግራፎች በ fig. 5 እና 6;

የሁለትዮሽ ግራፎች . የግራፍ ቋሚዎች ስብስብ በሁለት የማይነጣጠሉ ንዑስ ክፍሎች V 1 እና V 2 ሊከፈል እንደሚችል አስብ ስለዚህ በጂ ውስጥ ያለው እያንዳንዱ ጠርዝ ከ V 1 የተወሰነውን ከ V 2 የተወሰነ ጫፍ ጋር ያገናኛል (ምስል 7);

ከዚያም G የሁለትዮሽ ግራፍ ይባላል. እንደነዚህ ያሉት ግራፎች አንዳንድ ጊዜ ሁለት የተገለጹ ንዑስ ክፍሎችን ለመለየት ከፈለጉ በ G (V 1, V 2) ይገለጻሉ. የሁለትዮሽ ግራፍም በሌላ መንገድ ሊገለጽ ይችላል፣ ጫፎቹን በሁለት ቀለም በመቀባት ቀይ እና ሰማያዊ ይበሉ። ከዚህም በላይ ግራፍ እያንዳንዱ ጫፍ ቀይ ወይም ሰማያዊ ቀለም ሊኖረው የሚችል ከሆነ, የትኛውም ጠርዝ አንድ ጫፍ ቀይ እና ሌላኛው ጫፍ ሰማያዊ ከሆነ, ቢፓርትይት ይባላል. በሁለትዮሽ ግራፍ ውስጥ ከ V 1 እያንዳንዱ ጫፍ በእያንዳንዱ ጫፍ ከ V 2 ጋር መገናኘቱ ምንም አስፈላጊ እንዳልሆነ አጽንዖት ሊሰጠው ይገባል. ጉዳዩ ይህ ከሆነ እና ግራፉ G ቀላል ከሆነ, ከዚያም ይባላል የተሟላ የሁለትዮሽ ግራፍእና አብዛኛውን ጊዜ ይገለጻል

የት m , n በቅደም ተከተል በ V 1 እና V 2 ውስጥ ያሉት የቁመቶች ብዛት ናቸው. ለምሳሌ, በ fig. 8 ግራፍ K 4, 3 ያሳያል. ግራፉ መሆኑን ልብ ይበሉ
በትክክል m + n ጫፎች እና mn ጠርዞች አሉት። የቅጹ ሙሉ የሁለትዮሽ ግራፍ
የኮከብ ግራፍ ይባላል; በለስ ውስጥ. 9 የኮከብ ግራፍ ያሳያል
.

የተገናኙ ግራፎች . ግራፍ የተገናኘ፣እንደ ሁለት ግራፎች አንድነት መወከል ካልቻለ እና የማይጣጣምአለበለዚያ. በግልጽ ለማየት እንደሚቻለው ማንኛውም የተቋረጠ ግራፍ G እንደ ውሱን የተገናኙ ግራፎች ጥምረት ሊወከል ይችላል - እያንዳንዳቸው የተገናኙ ግራፎች ይባላሉ አካል (ግንኙነት)ግራፍ ጂ. (ስእል 10 ሶስት አካላት ያለው ግራፍ ያሳያል.) ብዙውን ጊዜ ለዘፈቀደ ግራፎች የተወሰኑ መግለጫዎችን ለተገናኙ ግራፎች መጀመሪያ ማረጋገጥ እና ከዚያም በእያንዳንዱ ክፍል ላይ በተናጠል መተግበር ምቹ ነው.

ሳይክል ግራፎች እና ጎማዎች . የተገናኘ የዲግሪ 2 መደበኛ ግራፍ ይባላል ሳይክል ግራፍ(ወይም ዑደት);ሳይክል ግራፍ. ከ ፒጫፎች በ C n ይገለጻሉ. ግራፎችን በማገናኘት ላይ እና
(ፒ≥ 3) ይባላል መንኮራኩርከ ፒጫፎች እና ይገለጻል ወ n . በለስ ላይ. 11 ተመስሏል ጋር 6 እና ወ 6 ; ግራፍ ወ 4 አስቀድሞ በስእል ውስጥ ታየ. 2.

3. የዩለር ግራፎች

የተገናኘ ግራፍ G ይባላል ኡለር፣በእያንዳንዱ ጠርዝ በኩል የሚያልፍ የተዘጋ ሰንሰለት ካለ; እንዲህ ዓይነቱ ወረዳ ይባላል የኡለር ሰንሰለት።ይህ ፍቺ እያንዳንዱ ጠርዝ አንድ ጊዜ ብቻ መሻገር እንዳለበት ልብ ይበሉ. በሰንሰለቱ መዘጋት ላይ ያለውን ገደብ ካስወገድን, ከዚያም ግራፉ ይባላል ግማሽ-ኡለር;በተጨማሪም፣ እያንዳንዱ የኡለር ግራፍ ከፊል-ኢዩለርያን ይሆናል። በለስ ላይ. 13፣14፣15 ኢዩለር ያልሆኑት፣ ከፊል-ኡለር እና ኡለር ግራፎች በቅደም ተከተል ይታያሉ።

ይህ ስም የበለስ ላይ የሚታየውን ግራፍ ለማወቅ አስፈላጊ ነበር ይህም ውስጥ ታዋቂ Königsberg ድልድይ ችግር ለመፍታት Euler የመጀመሪያው ነበር እውነታ ምክንያት "Eulers" ተነሣ. 15, የኡለር ሰንሰለት (የለውም). ጥያቄው ወዲያውኑ ይነሳል-ግራፍ ኡለር ለመሆን አስፈላጊ እና በቂ ሁኔታዎችን ማግኘት ይቻላል?

አንድ ቀላል ሌማ እናረጋግጥ።

ለማ 1. የግራፍ G የእያንዳንዱ ጫፍ ደረጃ ቢያንስ ሁለት ከሆነ G ዑደት ይይዛል።

ማረጋገጫ። ግራፉ G loops ወይም በርካታ ጠርዞችን ከያዘ ፣መግለጫው ግልፅ ነው ። ስለዚህ G ቀላል ግራፍ ነው እንበል። v የግራፍ G የዘፈቀደ ጫፍ ይሁን; መንገድን በማስተዋወቅ ከ v አጠገብ ያለውን ወርድ v 1 በመምረጥ እና ለ i ≥1 ፣ ከ v i አጠገብ ያለውን v i +1 በመምረጥ እና ከ v i -1 የተለየ (እንዲህ ያለ ቁልቁል v i +1 መኖር በሌማ ሁኔታ የተረጋገጠ ነው) . G የተገደበ የቋሚዎች ብዛት ስላለው፣ ከዚህ በፊት ከተመረጠው ጫፍ ጋር እንጨርሳለን። ቁ k የመጀመሪያው እንዲህ ያለ vertex ነው እንበል; ከዚያም በ v h ሁለት ክስተቶች መካከል ያለው የመንገዱ ክፍል አስፈላጊው ዑደት ነው.

ቲዎረም 1. የተገናኘ ግራፍ G Euler ነው, እና በ G ውስጥ ያለው እያንዳንዱ ጫፍ እኩል ዲግሪ ካለው ብቻ ነው.

ማረጋገጫ።
P በግራፍ ጂ የኡለር መንገድ እንደሆነ አስቡት። ከዚያም በእያንዳንዱ የ ሰንሰለቱ መተላለፊያ P በየትኛውም የግራፍ ጫፎች በኩል, የዚህ ወርድ ደረጃ በሁለት ይጨምራል. እና እያንዳንዱ ጠርዝ በፒ ውስጥ አንድ ጊዜ በትክክል ስለሚከሰት እያንዳንዱ ጫፍ እኩል የሆነ ደረጃ ሊኖረው ይገባል.

በጂ ውስጥ ባሉት የጠርዝ ብዛት ላይ በማስተዋወቅ ማረጋገጫውን እናከናውናለን. G የተገናኘ በመሆኑ የእያንዳንዱ ወርድ ዲግሪ ቢያንስ ሁለት ነው, እና ስለዚህ, በቀድሞው ሌማ, ግራፍ G ዑደት አለው ብለን እንደምደዳለን. ; ካልሆነ፣ ከጂ የዑደቱ C የሆኑትን ጠርዞች ስናስወግድ፣ አዲስ (ምናልባትም ተቋርጧል) ግራፍ እናገኛለን H. በ H ውስጥ ያሉት የጠርዝ ብዛት ከጂ ያነሰ ነው፣ እና በH ውስጥ ያለው ማንኛውም ጫፍ አሁንም እኩል ዲግሪ አለው። እንደ ኢንዳክቲቭ መላምት, እያንዳንዱ የግራፍ H አካል የዩለር ሰንሰለት ይዟል. በግራፍ ጂ ግኑኝነት ምክንያት በH ውስጥ ያለው እያንዳንዱ አካል ቢያንስ አንድ የጋራ ቋት ከዑደት C ጋር ስላለው የሚፈለገውን የግራፍ G የኡለር ሰንሰለት እንደሚከተለው ማግኘት ይቻላል፡ እስከ ዑደቱ C ጠርዝ ድረስ እንሄዳለን። የግራፍ ኤች የማይገለል ጫፍን እንገናኛለን፣ ከዚያም የተጠቆመውን ጫፍ የያዘውን የዚያ አካል የዩለር ሰንሰለት እንከተላለን። ከዚያም ሌላ የግራፍ H አካል የሆነ ጫፍ እስክንገናኝ ድረስ መንገዱን በዑደቱ ጠርዝ በኩል እንቀጥላለን C እና ወዘተ; ወደ መጀመሪያው ጫፍ ስንመለስ ሂደቱ ያበቃል (ምሥል 17).

ማጠቃለያ 1. የተገናኘው ግራፍ Euler ነው, እና የእሱ ጠርዝ ቤተሰብ ወደ ተለያዩ ዑደቶች መከፋፈል ከተቻለ ብቻ ነው.

ማጠቃለያ 2. የተገናኘው ግራፍ ከፊል-Eulerian ነው እና ቢበዛ ሁለት የጎዶሎ ዲግሪ ያለው ከሆነ ብቻ።

4. የግራፍ ቲዎሪ አፕሊኬሽኖች ምሳሌዎች

1. "የመጓጓዣ" ችግሮች, የግራፉ ጫፎች ነጥቦች ናቸው, እና ጠርዞቹ መንገዶች (መንገዶች, የባቡር ሀዲዶች, ወዘተ) እና / ወይም ሌላ የትራንስፖርት (ለምሳሌ አቪዬሽን) መንገዶች ናቸው. ሌላው ምሳሌ ደግሞ የአቅርቦት ኔትወርኮች (የኃይል አቅርቦት, የጋዝ አቅርቦት, የእቃ አቅርቦት, ወዘተ) ናቸው, በዚህ ውስጥ ጫፎቹ የምርት እና የፍጆታ ነጥቦች ናቸው, እና ጠርዞቹ የእንቅስቃሴዎች ሊሆኑ የሚችሉ መንገዶች (የኤሌክትሪክ መስመሮች, የጋዝ ቧንቧዎች, መንገዶች, ወዘተ) ናቸው. ወዘተ)። የጭነት ፍሰቶችን የማመቻቸት፣ የምርት እና የፍጆታ ነጥቦችን የመለየት፣ ወዘተ የችግሮች ተጓዳኝ ክፍል አንዳንድ ጊዜ የአቅርቦት ችግር ወይም የመገኛ ችግር ይባላል። የእነሱ ንዑስ ክፍል ስለ ጭነት መጓጓዣ ችግሮች ናቸው.

2. "የቴክኖሎጂ ተግባራት", ጫፎች የምርት ክፍሎችን (ፋብሪካዎች, ዎርክሾፖች, የማሽን መሳሪያዎች, ወዘተ) የሚያንፀባርቁበት, እና ቅስቶች በመካከላቸው የጥሬ እቃዎች, ቁሳቁሶች እና ምርቶች ፍሰቶች ናቸው, ትክክለኛውን ጭነት ለመወሰን ነው. የምርት ክፍሎችን እና ይህንን ጭነት የሚያረጋግጡ ፍሰቶች.

3. የልውውጥ እቅዶች፣ እንደ ባርተር፣ ማካካሻ፣ ወዘተ ያሉ ክስተቶች ሞዴሎች ናቸው። በዚህ ጉዳይ ላይ ያለው የግራፍ ጫፎች የልውውጥ እቅድ (ሰንሰለት) ተሳታፊዎችን ይገልፃሉ, እና አርከሮች በመካከላቸው የቁሳቁስ እና የፋይናንስ ሀብቶች ፍሰቶችን ይገልፃሉ. ሥራው ለምሳሌ የልውውጡ አደራጅ እና በሰንሰለቱ ውስጥ ካሉ ተሳታፊዎች ፍላጎቶች እና ነባር ገደቦች አንጻር ሲታይ ጥሩውን የልውውጥ ሰንሰለት መወሰን ነው ።

4. የፕሮጀክት አስተዳደር. (ፕሮጀክት ማኔጅመንት የለውጥ አስተዳደር ዘዴዎችን እና ዘዴዎችን የሚያጠና የአስተዳደር ንድፈ ሐሳብ ክፍል ነው (ፕሮጀክት በተወሰነ ስርዓት ውስጥ ዓላማ ያለው ለውጥ ነው ፣ በተጠቀሰው ጊዜ እና ግብዓት ገደብ ውስጥ ይከናወናል ፣ የማንኛውም ፕሮጀክት ባህሪ ልዩነቱ ነው) , ማለትም, ተዛማጅ ለውጦች ሕገወጥነት.)). ከግራፍ ንድፈ ሐሳብ እይታ አንጻር, አንድ ፕሮጀክት በመካከላቸው የተግባር እና ጥገኛዎች ስብስብ ነው. የመማሪያ መጽሀፍ ምሳሌ የአንድ ነገር የግንባታ ፕሮጀክት ነው. የግራፍ ንድፈ ሃሳብ ቋንቋን እና ውጤቶችን የሚጠቀሙ እና የፕሮጀክት አስተዳደር ችግሮችን ለመፍታት የሚያቀኑ የሞዴሎች እና ዘዴዎች ስብስብ የቀን መቁጠሪያ-ኔትወርክ እቅድ እና አስተዳደር (KSPU) ይባላል። በ QSPU ማዕቀፍ ውስጥ የሥራውን ቅደም ተከተል የመወሰን እና በመካከላቸው ሀብቶችን የመመደብ ተግባራት ፣ ከተወሰኑ መመዘኛዎች (የፕሮጀክት ጊዜ ፣ ​​ወጪዎች ፣ ወዘተ) አንፃር ተፈትተዋል ።

5. በሶሺዮሎጂ ውስጥ ጥቅም ላይ የሚውሉ የቡድኖች እና ቡድኖች ሞዴሎች በሰዎች ወይም በቡድኖቻቸው ውክልና ላይ የተመሰረቱ ናቸው, እና በመካከላቸው ያለው ግንኙነት (ለምሳሌ, የትውውቅ ግንኙነቶች, እምነት, ርህራሄ, ወዘተ.) - በ. የጠርዝ ወይም የአርከስ ቅርጽ. በእንደዚህ አይነት መግለጫ ማዕቀፍ ውስጥ የማህበራዊ ቡድኖችን መዋቅር የማጥናት, የማነፃፀር, የውጥረት, ወጥነት, መስተጋብር, ወዘተ የሚያንፀባርቁ አጠቃላይ አመልካቾችን የመወሰን ተግባራት ተፈትተዋል.

6. የድርጅታዊ መዋቅሮች ሞዴሎች, ጫፎቹ የአደረጃጀት ስርዓት አካላት ናቸው, እና ጠርዞች ወይም ቅስቶች በመካከላቸው ያሉ ግንኙነቶች (መረጃ, ቁጥጥር, ቴክኖሎጂ, ወዘተ) ናቸው.

5. አጭሩ መንገድ ችግር

ምሳሌ 1. ስለ ተኩላ, ፍየል እና ጎመን ችግር. ፍየሉ፣ ጎመን እና ተኩላ በወንዙ ዳርቻ ላይ ናቸው; ጀልባው ወንዙን አቋርጦ ሊወስዳቸው ይገባል፣ ነገር ግን ጀልባው በጣም ትንሽ ስለሆነ ከእነዚህ ሶስት "መንገደኞች" ውስጥ ከአንዱ በላይ ሊወስድ አይችልም። ግልጽ በሆኑ ምክንያቶች, ፍየል ያለው ተኩላ, እና ፍየል ከጎመን ጋር, ያለ ምንም ክትትል ሊተው አይችልም. አጓዡ ምን ማድረግ አለበት?

ይህ በጣም የታወቀው ችግር በቀላሉ ሊታሰብባቸው የሚገቡ አማራጮች አነስተኛ ቁጥር በመኖሩ በአእምሮ ውስጥ በቀላሉ ይፈታል, ሆኖም ግን, አጭር መንገድ ስለማግኘት ችግር የተለመደ ምሳሌ አለን: በስእል 1 ላይ የሚታየው ግራፍ ተስሏል እና የሚመራው መንገድ. ከቦታው a ሲፈለግ (ፍየል ኬ ፣ ጎመን ካፕ ፣ ተኩላ B እና ተሸካሚ P በቀኝ ባንክ ላይ ሲሆኑ) ወደ ቦታ ለ (ሁሉም ወደ ግራ ባንክ ሲዘዋወር) ፣ የሚፈለገው መንገድ በስዕሉ ላይ በወፍራም ይታያል ። መስመሮች.

በአጠቃላይ ስልታዊ ስልተ-ቀመር ያስፈልጋል, በርካታ ዘዴዎችን እናቀርባለን.

የአጭሩ መንገድ ችግር

የ n + 1 እርከኖች አውታረመረብ ይስጥ ፣ ማለትም ፣ ሁለት ጫፎች የሚመረጡበት ቀጥተኛ ግራፍ - ግብዓት (ዜሮ ወርድ) እና ውፅዓት (በቁጥር n)። ለእያንዳንዱ ቅስት ቁጥሮች ተሰጥተዋል, የአርክስ ርዝመቶች ይባላሉ. የመንገዱን ርዝመት (ኮንቱር) በውስጡ የተካተቱት የአርክስ ርዝመቶች ድምር ነው

(የአርከሮቹ ርዝማኔዎች ካልተገለጹ, የመንገዱን ርዝመት (ኮንቱር) በውስጡ የተካተቱት የአርከስ ብዛት ይገለጻል). ስራው ከግቤት ወደ አውታረ መረቡ ውፅዓት በጣም አጭር መንገድ (የዝቅተኛው ርዝመት መንገድ) ማግኘት ነው።

ለአጭር መንገድ መኖር, በኔትወርኩ ውስጥ አሉታዊ ርዝመት ያላቸው ቅርጾች እንዳይኖሩ አስፈላጊ እና በቂ ነው.

በአውታረ መረቡ ውስጥ ምንም ቀለበቶች እንደሌሉ አስቡ። ከዚያም ለማንኛውም ቅስት (i, j) j > i እንዲኖረን ሁልጊዜም ጫፎችን መቁጠር ይቻላል. እንዲህ ዓይነቱ ቁጥር ትክክለኛ ተብሎ ይጠራል. ኮንቱር በሌለበት አውታረ መረብ ውስጥ ሁል ጊዜ ትክክለኛ የቁጥር አቆጣጠር እንዳለ ማሳየት ቀላል ነው።

አመልክት። - የአርክ ርዝመት (i; j)። ትክክለኛው ቁጥር ያለው አውታረ መረብ ውስጥ ያለው አጭሩ መንገድ በሚከተለው ስልተ ቀመር ይወሰናል።

አልጎሪዝም 1.

;

ደረጃ k፡ vertex k በመረጃ ጠቋሚ ምልክት አድርግ
እኔ

መውጫ ኢንዴክስ ከአጭሩ መንገድ ርዝመት ጋር እኩል ይሆናል. (አልጎሪዝም 1 ለተለዋዋጭ የፕሮግራም አወጣጥ ችግሮች የቤልማንን የተመቻቸ መርህ ያንፀባርቃል፡- በሁለት ነጥቦች መካከል ያለውን አጭሩን መንገድ የምትፈልጉ ከሆነ፣በሁለት ነጥቦች መካከል ያለው የመንገዱ ርዝመት በጣም ዝቅተኛ መሆን አለበት።) ምስል 2 አንድ ምሳሌ ያሳያል። አጭሩን መንገድ ለመወሰን አልጎሪዝም 1 ን መተግበር (ቁጥሮች y arcs ከ arc ርዝመቶች ጋር እኩል ናቸው ፣ የወርድ ኢንዴክሶች በካሬ ቅንፎች ውስጥ ይቀመጣሉ ፣ አጭሩ መንገድ በድርብ መስመሮች ምልክት ተደርጎበታል)።

ኢንዴክሶች (በአንዳንድ ችግሮች ውስጥ የቬርቴክስ አቅም ይባላሉ) ሲመሰረቱ፣ አጭሩ መንገድ የሚወሰነው ከውጤቱ ወደ ግብአት ባለው የኋላ ትራኪንግ ዘዴ ማለትም አጭሩ መንገድ ነው።
, ለምሳሌ
ወዘተ.

የሚከተለው ስልተ-ቀመር በአጠቃላይ ሁኔታ (ማለትም በዘፈቀደ የጫፍ ቁጥሮች) ውስጥ አጭሩን መንገድ ለመወሰን ያስችላል።

አልጎሪዝም 2 (የፎርድ አልጎሪዝም)።

ደረጃ 0፡ የዜሮውን ጫፍ በመረጃ ጠቋሚ ምልክት ያድርጉበት
፣ ሁሉም ሌሎች ጫፎች ኢንዴክሶች ናቸው።
, i = 1, n;

ደረጃ k: ሁሉንም ቅስቶች ግምት ውስጥ ያስገቡ. ለቅስት ከሆነ (i; j)
>, ከዚያም አዲሱን ዋጋ እናሰላለን
;

ኢንዴክሶች በተወሰነ የእርምጃዎች ብዛት ተቀምጠዋል። አመልክት።
- ቋሚ-ግዛት ጠቋሚ እሴቶች, የሚከተለው ንብረት ያላቸው: እሴቱ ከዜሮ ወርድ እስከ i vertex ካለው አጭር መንገድ ርዝመት ጋር እኩል ነው። ከ vertex 0 እስከ vertex i ያለው አጭሩ መንገድ የሚወሰነው በኋለኛው የክትትል ዘዴ ነው።

የሁሉም ቅስቶች ርዝማኔዎች አሉታዊ ካልሆኑ, የሚከተለው ስልተ ቀመር አጭሩን መንገድ ለማግኘት ተፈጻሚ ይሆናል.

አልጎሪዝም 3.

ደረጃ 0፡ የዜሮውን ጫፍ በመረጃ ጠቋሚ ምልክት ያድርጉበት
;

ደረጃ k፡ አንዳንድ የቁመቶች ስብስብ አስቀድሞ ምልክት ይደረግበት። Q ከተሰየሙት አጠገብ ያሉ ያልተሰየሙ ጫፎች ስብስብ ይሁን። ለእያንዳንዱ ጫፍ
እሴቱን አስሉ
ዝቅተኛው በሁሉም የተሰየሙ ጫፎች ላይ የሚወሰድበት i ከ vertext k አጠገብ። ዋጋው ለየትኛው ጫፍ k ምልክት እናደርጋለን ዝቅተኛ, ኢንዴክስ
.

የ vertext n ምልክት እስኪደረግ ድረስ ይህን አሰራር እንደግመዋለን. የአጭሩ መንገድ ርዝመት ነው። , እና አጭሩ መንገድ ራሱ ከላይ እንደተገለፀው ይገለጻል.

በተመሳሳይም ከአጭሩ መንገድ ችግር ጋር የከፍተኛው (ረዥሙ) መንገድ ችግር ተቀርጾ ተፈትቷል - የአርክስ ምልክቶችን ወደ ተቃራኒዎች መለወጥ እና የአጭር መንገድን ችግር መፍታት በቂ ነው። ለከፍተኛው የመንገድ ችግር መፍትሄ መኖር, አስፈላጊ እና በቂ የሆነ አወንታዊ ርዝመት ያላቸው ቅርጾች እንዳይኖሩ በቂ ነው.

በከፍተኛው አስተማማኝነት መንገድ የማግኘት ችግር, የአርሴስ ርዝማኔዎች ይተረጎማሉ, ለምሳሌ, በተዛማጅ ሁለት ነጥቦች መካከል ግንኙነት ሊኖርባቸው የሚችሉ እድሎች. የአርሶቹን ርዝማኔዎች በሎጋሪዝምዎቻቸው በተገላቢጦሽ ምልክቶች በመተካት, በዋናው ግራፍ ውስጥ ያለው ከፍተኛው አስተማማኝነት መንገድ በአዲሱ ግራፍ ውስጥ ካለው አጭር መንገድ ጋር ይዛመዳል.

ምሳሌ 1

ሩዝ. 3. ለአጭር መንገድ ችግር የመጀመሪያ ውሂብ.

ሁኔታው በሚመራው ግራፍ ብቻ ሳይሆን በሠንጠረዥ (ሠንጠረዥ 1) ሊገለጽ ይችላል.

ሠንጠረዥ 1. ለአጭሩ መንገድ ችግር የመጀመሪያ ውሂብ

አርክ ጀምር

የቀስት መጨረሻ

የጉዞ ጊዜ

ጥያቄው፡ ከ 1 ኛ ጫፍ ወደ 4 ኛ ደረጃ ለመድረስ አጭሩ መንገድ ምንድነው?

ውሳኔ.ማስታወሻውን እናስተዋውቃለን: C (T) ከ vertex 1 እስከ vertex T. ቁጥር ያለው የአጭሩ መንገድ ርዝመት ነው, እና አነስተኛው የተገደበ የንጥረ ነገሮች ብዛት ሁልጊዜ ይደርሳል.) እየተገመገመ ያለው ችግር C (4) ማስላት ነው. እና ይህ ዝቅተኛው የሚደርስበትን መንገድ ያመልክቱ.

የበለስ ውስጥ ለቀረበው የመጀመሪያ ውሂብ. 3 እና በሠንጠረዥ ውስጥ. 1፣ አንድ ቀስት ብቻ ወደ ቬርቴክስ 3 ይገባል፣ ከ vertex 1፣ እና በዚህ ቀስት አቅራቢያ ርዝመቱ ከ 1 ጋር እኩል ነው ፣ ስለሆነም С(3)=1። በተጨማሪም, ግልጽ ነው С (1) = 0.

ከቬርቴክስ 2፣ ከ 4 ጋር እኩል በሆነ መንገድ ወይም ከ 5 ጋር እኩል በሆነ መንገድ ተጉዘህ 4 ላይ መድረስ ትችላለህ። ስለዚህ፣ ዝምድና С(4) = ደቂቃ (С(2) + 4; С(5) + 5)።

ስለዚህ የችግሩን መልሶ ማዋቀር ተካሂዷል - С(4) ማግኘት С(2) እና С(5) ማግኘት ቀንሷል።

ከ 3 ጋር እኩል በሆነ መንገድ ተጉዘህ ወይም ከ 6 ጋር እኩል በሆነ መንገድ ተጉዘህ ወደ 5ኛው ጫፍ መድረስ ትችላለህ።ስለዚህ ግንኙነቱ С(5) = ደቂቃ (С(3) + 2; С(6) + 3)።

እኛ እናውቃለን C (3) = 1. ስለዚህ, C (5) = ደቂቃ (3; C (6) + 3).

ሐ(6) አወንታዊ ቁጥር መሆኑ ግልጽ ስለሆነ፣ ከመጨረሻው ዝምድና ሲ(5) = 3 ይከተላል።

ከ vertext 1 ወደ 2 ኛ ደረጃ መድረስ ይችላሉ ፣ ከ 7 ጋር እኩል በሆነ መንገድ ተጉዘዋል ፣ ወይም ከ vertex 3 ፣ ከ 5 ጋር እኩል የሆነ መንገድ ተጉዘዋል ፣ ወይም ከ 5 ጋር እኩል በሆነ መንገድ ተጉዘዋል ፣ 2 እኩል በሆነ መንገድ ተጉዘዋል ። ስለዚህ ፣ ግንኙነቱ С (2) = ደቂቃ (С( 1) + 7፤ ሲ (3) + 5፤ ሲ (5) + 2)።

እኛ እናውቃለን С(1) = 0, С(3) = 1, С(5) = 3. ስለዚህ, С(2) = ደቂቃ (0 + 7; 1 + 5; 3 + 2) = 5.

አሁን C (4): C (4) = ደቂቃ (C (2) + 4; C (5) + 5) = ደቂቃ (5 + 4; 3 + 5) = 8 ማግኘት እንችላለን.

ስለዚህም የአጭሩ መንገድ ርዝማኔ 8. ከመጨረሻው ግኑኝነት ወደ ቬርቴክስ 4 እስከ ቬቴክስ 5 መሄድ እንዳለብን ግልጽ ነው ወደ ሲ(5) ስሌት ስንመለስ ወደ ቬርቴክስ 5 መሄድ እንዳለብን እናያለን። vertex 3. እና ወደ ቬርቴክስ 3 ልንደርስ የምንችለው ከመስቀለኛ መንገድ ብቻ ነው 1. ስለዚህ አጭሩ መንገድ 1 → 3 → 5 → 4 ነው።

ለተወሰኑ የመጀመሪያ መረጃዎች (ምስል 3 እና ሠንጠረዥ 1) የአጭሩ መንገድ ችግር ሙሉ በሙሉ ተፈትቷል.

ምሳሌ 2

ከአካዳምጎሮዶክ (Tsvetnoy proezd አቁም) ወደ ባቡር ጣቢያው አጭሩ መንገድ (የመንገዱን ርዝመት) ያግኙ።

ማቆሚያዎች፡

ባለቀለም መተላለፊያ

የሕይወት ቤት

3.3" - የኑክሌር ፊዚክስ ተቋም

4 መታጠቢያ ቁጥር 22

5 ወንዝ ጣቢያ

6 - ዘሪ

7 - ካፌ "ስፓርክ"

8 - ድልድይ

9 - ዋና ጣቢያ

ከኖድ 1 እስከ መስቀለኛ መንገድ 9 ያለውን አጭር መንገድ ያግኙ።

የመጀመሪያ ውሂብ፡-

ሩዝ. 4

ትር. 2

አርክ ጀምር

የቀስት መጨረሻ

የመንገዱ ርዝመት (ኪሜ)

3,06

10,9

26,78

21,57

4,26

4,35

2,55

መፍትሔው፡ C (T) ከኖድ 1 እስከ መስቀለኛ መንገድ ቲ ያለው አጭሩ መንገድ ርዝመት ነው። C (9) ማግኘት አለብን።

C(1)=0፣ C(2)=3 (አንድ ቀስት ብቻ ወደ ቬርቴክስ 2 ይገባል፣ ርዝመቱ 3 ነው)።

ጫፍ 9 ከቬርቴክስ 5, መንገዱን 4.35, ከቬርቴክስ 6, መንገዱን 25 እና ከ 8 ላይ በማለፍ, መንገዱን 2.55 ማለፍ ይቻላል.

ስለዚህ፣ С(9) = ደቂቃ (С(5) + 4.35፤ С(6) + 25፤ С(8) + 2.55)

ስለዚህ, С (5), С (6), С (8) ማግኘት አስፈላጊ ነው.

መንገዱን 19 በማለፍ መንገዱን 26.78 ወይም ከ vertext 7 ላይ በማለፍ ወደ 5 ኛ ደረጃ መድረስ ይችላሉ ።

С(5) = ደቂቃ (С(1) + 26.78፤ С(7) + 19)

C (7) ማግኘት አስፈላጊ ነው. Vertex 7 በ 7.6 በመሄድ ከ 3 ኢንች 7.6 በመሄድ ከ 3 ላይ መድረስ ይቻላል.

С(7) = ደቂቃ (С(3) + 7.6፤ С(3") + 7.6)= ደቂቃ (1.7+7.6፤ 3.06+7.6)=9.3

С(5) = ደቂቃ (26.78፤ 9.3+ 19)=26.78

ከ 0.5 ጋር እኩል የሆነ መንገድ በማለፍ ከ vertex 2 ወደ 6 ኛ ደረጃ መድረስ ይችላሉ

С(6)=С(2)+0.5=3+0.5=3.5

ጫፉ 8 መንገዱን 21.57 በማለፍ እና ከ 5 ኛው ጫፍ 4.62 በማለፍ ከ vertex 4 መድረስ ይቻላል.

С(8) = ደቂቃ (С(4) + 21.57፤ С(5) + 4.26)

С(4)=10.9 (ከሁኔታው)።

С(8) = ደቂቃ (10.09+ 21.57፤ 26.78 + 4.26)=31.4

በዚህም ምክንያት

С(9)= ደቂቃ (26.78+4.35፤ 3.5+25፤ 31.4+2.55)= ደቂቃ (31.13፤ 28.5፤ 33.95)=28.5

ስለዚህ, የአጭሩ መንገድ ርዝመት 28.5 ኪ.ሜ.

በጣም አጭር መንገድ፡ 1 → 2 → 6 → 9።

6. ከፍተኛውን ፍሰት ለማግኘት አልጎሪዝም

የዚህ ስልተ ቀመር ሀሳብ ከምንጩ ወደ ማጠቢያ ገንዳው አዎንታዊ ፍሰቶች ከጫፍ እስከ ጫፍ መንገዶችን ማግኘት ነው።

(የመጀመሪያ) አቅም ያለው ጠርዝ (i፣ j) አስቡበት
. በአልጎሪዝም አፈፃፀም ወቅት የእነዚህ የመተላለፊያ ይዘት ክፍሎች በዚህ ጠርዝ በኩል በሚያልፉ ፍሰቶች "ይወሰዳሉ", በዚህም ምክንያት እያንዳንዱ ጠርዝ ቀሪ የመተላለፊያ ይዘት ይኖረዋል. መቅዳት
- ቀሪ አቅም. ሁሉም ጠርዞች ቀሪ አቅም ያላቸውበት አውታረ መረብ ቀሪ ይባላል።

የዘፈቀደ መስቀለኛ መንገድ j , ከ node i ዥረት በመቀበል, መለያውን እንገልጻለን
፣ የት - ከኖድ j ወደ መስቀለኛ መንገድ i የሚፈሰው ፍሰት መጠን. ከፍተኛውን ፍሰት ለማግኘት, የሚከተሉትን ደረጃዎች ያከናውኑ.

ደረጃ 1.

ለሁሉም ጠርዞች, የተረፈውን አቅም ከመጀመሪያው አቅም ጋር እኩል እናዘጋጃለን, ማለትም. ማመሳሰል
=
. እንመድበው
እና መስቀለኛ መንገድ 1ን ከመለያ ጋር ይሰይሙ። እኔ = 1 አዘጋጅተናል.

ደረጃ 2.

- የአንጓዎች ስብስብ j , በአዎንታዊ ቀሪ አቅም በጠርዙ I ከኖድ መሄድ ይችላሉ. > 0 ለሁሉም j . ከሆነ
ደረጃ 3ን ያከናውኑ፣ አለበለዚያ ወደ ደረጃ 4 ይሂዱ።

ደረጃ 3.

አት እንደዚህ ያለ መስቀለኛ መንገድ ያግኙ
. እናስቀምጠው
እና በመስቀለኛ መንገድ k ምልክት ያድርጉ
. k =n ከሆነ, የመተላለፊያ መንገዱ ተገኝቷል እና ወደ 5 ኛ ደረጃ ይሂዱ, አለበለዚያ i =k እና ወደ 2 ኛ ደረጃ እንመለሳለን.

ደረጃ 4.

እንዲመለስ. እኔ =1 ከሆነ, መንገድ በኩል የሚቻል አይደለም, እና 6. ከሆነ
፣ የተለጠፈውን መስቀለኛ መንገድ r ወዲያውኑ ከኖድ i በፊት ይፈልጉ እና ከአንጓው አር አጠገብ ካሉት የአንጓዎች ስብስብ ያስወግዱት። i =r አስቀመጥን እና ወደ ደረጃ 2 እንመለሳለን።

ደረጃ 5.

ቀሪው የአውታረ መረብ ትርጉም
. pth ከምንጩ መስቀለኛ መንገድ (መስቀለኛ መንገድ 1) ወደ ማጠቢያ መስቀለኛ መንገድ (ኖድ n) በሚያልፍበት የኖዶች ስብስብ ያመልክቱ። ከዚያም በዚህ መንገድ የሚያልፍ ከፍተኛው ፍሰት

የመተላለፊያ መንገዱን የሚያካትቱት የጠርዝ ቀሪ አቅም በእሴቱ ቀንሷል ወደ ፍሰት አቅጣጫ እና በተቃራኒው አቅጣጫ በተመሳሳይ መጠን መጨመር.

ያ። ለዳር (i, j) በመተላለፊያው መንገድ ውስጥ የተካተተው, የአሁኑ ቀሪ ችሎታዎች ይለወጣሉ:

1)
ፍሰቱ ከኖድ i ወደ j የሚሄድ ከሆነ፣

2)
ፍሰቱ ከኖድ j ወደ i የሚሄድ ከሆነ.

ደረጃ 6.

ውሳኔ.

ሀ) በ ሜትር በመንገዶች በኩል ተገኝቷል, ከፍተኛው ፍሰት የሚገለጸው በ

ለ) የመነሻ ዋጋዎች መኖር
እና የመጨረሻ
የጠርዙን አቅም (i, j), በዚህ ጠርዝ በኩል ጥሩውን ፍሰት እንደሚከተለው ማስላት እንችላለን. ፍቀድ። ከሆነ > 0, በጠርዙ (i, j) ውስጥ የሚያልፈው ፍሰት እኩል ነው . ከሆነ > 0፣ ከዚያ ፍሰቱ ነው። . (ጉዳዩ በተመሳሳይ ጊዜ > 0 እና > 0, የማይቻል).

ምሳሌ 1. በአውታረ መረቡ ውስጥ ከፍተኛውን ፍሰት ያግኙ Fig. አንድ

መደጋገም 1.
=

1)
እና መስቀለኛ መንገድ 1ን ከመለያ ጋር ይሰይሙ
. እኔ = 1

2)

3) k =3 ጀምሮ። መድብ
እና መስቀለኛ መንገድ 3ን ከመለያ ጋር ይሰይሙ
. i =3 እና ወደ 2 ተመለስ)

4)

5) k = 5 እና . መስቀለኛ መንገድ 5 ከመለያ ጋር
. የመተላለፊያ መንገድ እናገኛለን.

6) የመተላለፊያ መንገዱ የሚወሰነው በስያሜዎች ሲሆን ከኖድ 5 ጀምሮ እና በመስቀለኛ 1: ያበቃል.
:

መደጋገም 2.

1)
እና መስቀለኛ መንገድ 1ን ከመለያ ጋር ይሰይሙ
. እኔ = 1

2)

3) k =2፣ እና ኖድ 2ን ከመለያው ጋር
. i =2 እና ወደ 2 ተመለስ)

2")

3") k =3 እና
. መስቀለኛ መንገድ 3 ከመለያ ጋር
. i =3 እና ወደ 2 ተመለስ)

2)
(
, ስለዚህ መስቀለኛ መንገድ 5 አልተካተተም

3) k=4,
እና መስቀለኛ መንገድ 4ን ከመለያ ጋር ይሰይሙ
. i =4 እና ወደ 2 ተመለስ)

2""")
(አንጓዎች 1 እና 3 የተሰየሙ ስለሆኑ አልተካተቱም። )

3""") k=5 እና
. መስቀለኛ መንገድ 5 ከመለያ ጋር
. የመተላለፊያ መንገድ ተቀብሏል። ወደ 5 ይሂዱ)

5)
እና. በመንገዱ ላይ ያሉ ቀሪ የመተላለፊያ ክፍሎችን በማስላት ላይ :

መደጋገም 3.

1)
እና መስቀለኛ መንገድ 1ን ከመለያ ጋር ይሰይሙ
. እኔ = 1

2)

3) k=2፣
እና መስቀለኛ መንገድ 2ን ከመለያ ጋር ይሰይሙ
. i =2 እና ወደ 2 ተመለስ)

2")

ሩዝ. 2. የመጀመሪያ መረጃ ለምሳሌ 2

በትራንስፖርት ስርዓቱ ላይ ያለው የመነሻ መረጃ, ለምሳሌ, በአትክልት ውስጥ, በ fig. 2 እንደ ጠረጴዛ ሊገለጽ ይችላል (ሠንጠረዥ 2).

ሠንጠረዥ 2. ለከፍተኛው ፍሰት ችግር የመጀመሪያ ውሂብ

የመነሻ ቦታ

መድረሻ

የመተላለፊያ ይዘት

ከመነሻ ነጥብ 0 ማለትም 2 ክፍሎች ወደ ነጥብ 1 ፣ 3 ክፍሎች ወደ ነጥብ 2 እና 1 አሃድ ወደ ነጥብ 3 መላክ ስለማይቻል የትራንስፖርት ስርዓቱ ከፍተኛው አቅም ከ 6 አይበልጥም ። በመቀጠልም ነጥብ 0 የቀሩት 6 ጭነት እቃዎች የመጨረሻው ነጥብ ላይ መድረሳቸውን ማረጋገጥ አለቦት 4. በግልጽ ለማየት እንደሚቻለው 2 ነጥብ 1 ላይ የደረሱ 2 ጭነት እቃዎች በቀጥታ ወደ ነጥብ 4 መላክ ይቻላል. መከፋፈል አለባቸው: 2 ክፍሎች ወዲያውኑ ወደ ነጥብ 4 ይሂዱ, እና 1 ክፍል - ወደ መካከለኛ ነጥብ 3 (በነጥብ 2 እና 4 መካከል ባለው የአቅም ውስንነት ምክንያት). የሚከተሉት ጭነቶች ወደ ነጥብ 3 ተደርገዋል፡ 1 አሃድ ከ ነጥብ 0 እና 1 አሃድ ከ ነጥብ 3. ወደ ነጥብ 4 እንልካቸዋለን.ስለዚህ የታሰበው የትራንስፖርት ስርዓት ከፍተኛው አቅም 6 ጭነት ነው. በተመሳሳይ ጊዜ በነጥቦች 1 እና 2 መካከል ያሉ የውስጥ ክፍሎች (ቅርንጫፎች) እንዲሁም በ 1 እና 3 መካከል ያሉት ክፍሎች ጥቅም ላይ አይውሉም ። የ 3 ክፍሎች ብዛት. መፍትሄው በሠንጠረዥ መልክ ሊቀርብ ይችላል (ሠንጠረዥ 3)

ሠንጠረዥ 3. ከፍተኛውን ፍሰት ችግር መፍታት

የመነሻ ቦታ

መድረሻ

የመጓጓዣ እቅድ

የመተላለፊያ ይዘት

የመስመራዊ የፕሮግራም አወጣጥ ችግር ፍሰትን ከፍ ለማድረግ።ከመስመር ፕሮግራሚንግ አንፃር ከፍተኛውን የፍሰት ችግር እንቅረፅ። X KM ከ K እስከ ነጥብ ኤም ያለው የትራፊክ መጠን ይሁን በ fig. 2 K = 0.1.2.3, M = 1.2.3.4, እና መጓጓዣ የሚቻለው ከፍ ያለ ቁጥር ወዳለው ነጥብ ብቻ ነው. ይህ ማለት በአጠቃላይ 9 ተለዋዋጮች X KM አሉ እነሱም X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, X 34. ፍሰቱን ከፍ ለማድረግ ያለመ መስመራዊ የፕሮግራም ችግር. ቅጽ አለው:

ረ → ከፍተኛ፣

X 01 + X 02 + X 03 = ረ(0)

– X 01 + X 12 + X 13 + X 14 = 0 (1)

– X 02 - X 12 + X 23 + X 24 = 0 (2)

– X 03 - X 13 - X 23 + X 34 = 0 (3)

– X 14 - X 24 - X 34 \u003d - ረ (4)

Х 01 ≤ 2

Х 02 ≤ 3

Х 03 ≤ 1

X 12 ≤ 4

X 13 ≤ 1

X 14 ≤ 3

X 23 ≤ 1

X 24 ≤ 2

X 34 ≤ 2

X KM ≥ 0, K, M = 0, 1, 2, 3, 4

ኤፍ 0.

እዚህ F የዓላማው ተግባር ነው, ሁኔታ (0) እቃዎችን ወደ ማጓጓዣ ስርዓት መግባቱን ይገልጻል. ሁኔታዎች (1) - (3) ለስርዓቱ 1-3 መስቀለኛ መንገድ ሚዛኑን ያዘጋጃሉ። በሌላ አገላለጽ ለእያንዳንዱ የውስጥ አንጓዎች መጪው የሸቀጦች ፍሰት ከሚወጣው ፍሰት ጋር እኩል ነው, ጭነቶች በሲስተሙ ውስጥ አይከማቹም እና በውስጡም "ያልተወለዱ" ናቸው. ሁኔታ (4) ከስርአቱ እቃዎች "መውጣት" ሁኔታ ነው. ከሁኔታ (0) ጋር አንድ ላይ በመሆን ለስርዓቱ በአጠቃላይ ሚዛን ("ግቤት" ከ "ውጤት") ጋር እኩል ነው). የሚቀጥሉት ዘጠኝ እኩልነቶች በትራንስፖርት ስርዓቱ የግለሰብ "ቅርንጫፎች" አቅም ላይ ገደቦችን ያስቀምጣሉ. ከዚያም የትራፊክ ጥራዞች እና ተጨባጭ ተግባራት አሉታዊ አለመሆን ይገለጻል. የመጨረሻው አለመመጣጠን ከዓላማው ተግባር (ግንኙነት (0) ወይም (4)) እና ከትራፊክ መጠኖች አሉታዊ አለመሆን እንደሚከተል ግልጽ ነው። ይሁን እንጂ የመጨረሻው አለመመጣጠን አንዳንድ አጠቃላይ መረጃዎችን ይይዛል - ወይም አወንታዊ የሸቀጦች መጠን በስርዓቱ ውስጥ ሊያልፍ ይችላል, ወይም ዜሮ (ለምሳሌ, በስርዓቱ ውስጥ በክበብ ውስጥ እንቅስቃሴ ካለ), ግን አሉታዊ አይደለም (ኢኮኖሚያዊ አያደርግም). ስሜት ፣ ግን ስለዚህ መደበኛ የሂሳብ ሞዴል “አያውቀውም”)።

ማጠቃለያ

በዚህ ጽሑፍ ውስጥ የግራፍ ንድፈ ሐሳብ ጥናትን እንድንቀጥል የሚያስችለንን አስፈላጊ የሆኑትን ዝቅተኛ ጽንሰ-ሐሳቦች ተመልክተናል. ለነገሩ፣ ኢኮኖሚያዊ ችግሮችን ለመፍታት ሁለት መንገዶችን በመመርመር የአንድ ግዙፍ የበረዶ ግግር ጫፍ ላይ ብቻ ነካን። የግራፍ ንድፈ ሐሳብ አንዳንድ የግለሰብ ክስተቶችን ወይም ሂደቶችን በማጥናት ብቻ የተገደበ አይደለም፤ በተለያዩ የሳይንስና ቴክኖሎጂ መስኮች ተግባራዊ ያደርጋል።

የአጭር መንገድን ችግር ለመፍታት እና ከፍተኛውን ፍሰት ለማግኘት ስልተ ቀመሮች ግምት ውስጥ ገብተዋል ፣ ምሳሌዎች ተንትነዋል። የእነሱ ምሳሌ የኢኮኖሚ ችግሮችን ለማመቻቸት የግራፍ ንድፈ ሃሳብ አስፈላጊነት አሳይቷል.

በተመሳሳይ መልኩ ከዕለት ተዕለት ሕይወታችን ጋር ቀጥተኛ ግንኙነት ስላለው አጭር መንገድ ምሳሌ ተዘጋጅቶ ተፈትቷል. ሥራው ከአካዳምጎሮዶክ (Tsvetnoy proezd ማቆሚያ) ወደ ዋናው ጣቢያ አጭሩ መንገድ (መንገዶች በኪሜ ርዝመት አላቸው) ማግኘት ነበር።

መጽሃፍ ቅዱስ

"ሶሮስ ትምህርታዊ ጆርናል" ቁጥር 11 1996 (አንቀጽ "ጠፍጣፋ ግራፎች");

"የሂሳብ መምህርን ለመርዳት", ዮሽካር-ኦላ, 1972, ገጽ. "የግራፍ ንድፈ ሐሳብ አካላትን ማጥናት"

በርጌ፣ ኬ.ኤስ. ግራፍ ቲዎሪ እና አፕሊኬሽኖቹ።/K. S. Berzh.- M.: IL, 2007.-178s.

ቡርኮቭ, ቪ.ኤን. የግራፍ ቲዎሪ አካላት።/V. N. Burkov. - ኤም.: መገለጥ, 2010.-352s.

ጋርድነር, ኤም.ኤስ. "የሂሳብ መዝናኛ". / M. S. ጋርድነር.- M.: "ሚር", 2004.-347p.

ጋርድነር፣ ኤም.ኤስ. "የሂሣብ እንቆቅልሽ እና መዝናኛ" / M S ጋርድነር.-ኤም. : "ሚር", 2005.-221s.

Zykov, A. A. የተጠናቀቁ ግራፎች ንድፈ ሃሳብ./ A. A. Zykov. - ኖቮሲቢርስክ: "ናኡካ", 2006.-257p.

ካሳትኪን, V. N. "ያልተለመዱ የሂሳብ ችግሮች" / V. N. Kasatkin.-Kyiv: "የራዲያን ትምህርት ቤት", 2007.-232p.

ኦሌክኒክ, ኤስ.ኤን. "የቆዩ አዝናኝ ችግሮች" / ሲ.ኤን. Olechnik.- M. "ሳይንስ", 2008.-431s.

ኦሬ፣ ኦ.ኤስ. "ግራፎች እና መተግበሪያዎቻቸው"/ኦ. ኤስ ኦሬ - ኤም .: "ሚር", 2005-269 ዎች.

ሬኒ፣ ኤ.ኤን. "የሒሳብ ትሪሎሎጂ"

ሙሉ በሙሉ የተቆራረጡ ግራፎች . የጠርዝ ስብስብ ባዶ የሆነ ግራፍ ይባላል በጣም የማይጣጣም(ወይም ባዶ) ግራፍ.ሙሉ በሙሉ የተቋረጠ ግራፍ ከ n ጫፎች ጋር በ N n እናሳያለን; ቁጥር 4 በስእል ውስጥ ይታያል. 1. ልብ ይበሉ በሙሉ በሙሉ የተቋረጠ ግራፍ ፣ ሁሉም ጫፎች የተገለሉ ናቸው። ሙሉ በሙሉ የተቆራረጡ ግራፎች ብዙም ፍላጎት የላቸውም።

የተሟሉ ግራፎች . ማንኛውም ሁለት ጫፎች አጠገብ ያሉበት ቀላል ግራፍ ይባላል የተሟላ ግራፍ.የተሟላ ግራፍ ከ n ጫፎች ጋር ብዙውን ጊዜ የሚገለጸው በ። ግራፎች እና በ fig. 2 እና 3. በትክክል n (n - 1) / 2 ጠርዞች አሉት.

መደበኛ ግራፎች . ሁሉም ጫፎች ተመሳሳይ ዲግሪ ያላቸው ግራፍ ይባላል መደበኛ ግራፍ.የእያንዳንዱ ጫፍ ደረጃ r ከሆነ, ከዚያም ግራፉ ይባላል መደበኛ ዲግሪ r.የዲግሪ 3 መደበኛ ግራፎች, እንዲሁም ይባላል ኪዩቢክ(ወይም ትራይቫለንት)ግራፎች (ለምሳሌ, ምስል 2 እና 4 ይመልከቱ). ሌላው በጣም የታወቀ የኩቢክ ግራፍ ምሳሌ ተብሎ የሚጠራው ነው ፒተርሰን ቆጠራበለስ ላይ ይታያል. 5. እያንዳንዱ ሙሉ በሙሉ የተቋረጠ ግራፍ መደበኛ ደረጃ 0 መሆኑን እና እያንዳንዱ ሙሉ ግራፍ K n የዲግሪ n - 1 መደበኛ መሆኑን ልብ ይበሉ።

የፕላቶኒክ ግራፎች . ከመደበኛ ግራፎች መካከል የፕላቶኒክ ግራፊክስ የሚባሉት በተለይ ትኩረት የሚስቡ ናቸው - በአምስት መደበኛ የ polyhedra ጫፎች እና ጠርዞች የተሠሩ ግራፎች - የፕላቶኒክ ጠጣር-ቴትራሄድሮን ፣ ኩብ ፣ ኦክታድሮን ፣ ዶዲካሄድሮን እና ኢኮሳሄድሮን። ግራፉ ከ tetrahedron (ምስል 2) ጋር ይዛመዳል; ከኩብ እና ከ octahedron ጋር የሚዛመዱ ግራፎች በ fig. 5 እና 6;

የሁለትዮሽ ግራፎች . የግራፍ ጫፎች ስብስብ በሁለት የማይነጣጠሉ ንዑስ ክፍሎች V 1 እና V 2 ሊከፈል እንደሚችል እናስብ በ G ውስጥ ያለው እያንዳንዱ ጠርዝ የተወሰነውን ከ V 1 የተወሰነውን ከ V 2 (ምስል 7) ጋር ያገናኛል;

ከዚያም G የሁለትዮሽ ግራፍ ይባላል. እንደነዚህ ያሉት ግራፎች አንዳንድ ጊዜ ሁለት የተገለጹ ንዑስ ክፍሎችን ለመለየት ከፈለጉ በ G (V 1, V 2) ይገለጻሉ. የሁለትዮሽ ግራፍም በሌላ መንገድ ሊገለጽ ይችላል፣ ጫፎቹን በሁለት ቀለም በመቀባት ቀይ እና ሰማያዊ ይበሉ። ከዚህም በላይ ግራፍ እያንዳንዱ ጫፍ ቀይ ወይም ሰማያዊ ቀለም ሊኖረው የሚችል ከሆነ, የትኛውም ጠርዝ አንድ ጫፍ ቀይ እና ሌላኛው ጫፍ ሰማያዊ ከሆነ, ቢፓርትይት ይባላል. በሁለትዮሽ ግራፍ ውስጥ ከ V 1 እያንዳንዱ ጫፍ በእያንዳንዱ ጫፍ ከ V 2 ጋር መገናኘቱ አስፈላጊ እንዳልሆነ አጽንዖት ሊሰጠው ይገባል. ጉዳዩ ይህ ከሆነ እና ግራፉ G ቀላል ከሆነ, ከዚያም ይባላል የተሟላ የሁለትዮሽ ግራፍእና ብዙውን ጊዜ የሚወከለው m, n በ V 1 እና V 2 ውስጥ ያሉት የቁመቶች ብዛት ናቸው. ለምሳሌ, በ fig. 8 ግራፍ K 4, 3 ያሳያል. ግራፉ በትክክል m + n ጫፎች እና mn ጠርዞች እንዳለው ልብ ይበሉ። የተሟላ የሁለትዮሽ እይታ ግራፍ ኮከብ ግራፍ ይባላል; በለስ ውስጥ. 9 የኮከብ ግራፍ ያሳያል.

የተገናኙ ግራፎች . ግራፍ የተገናኘ፣እንደ ሁለት ግራፎች አንድነት መወከል ካልቻለ እና የማይጣጣምአለበለዚያ. በግልጽ ለማየት እንደሚቻለው ማንኛውም የተቋረጠ ግራፍ G እንደ ውሱን የተገናኙ ግራፎች ጥምረት ሊወከል ይችላል - እያንዳንዳቸው የተገናኙ ግራፎች ይባላሉ አካል (ግንኙነት)ግራፍ G. (ስእል 10 ሶስት አካላት ያለው ግራፍ ያሳያል.) ብዙውን ጊዜ ለዘፈቀደ ግራፎች የተወሰኑ መግለጫዎችን ለተገናኙ ግራፎች መጀመሪያ ማረጋገጥ እና ከዚያም በእያንዳንዱ ክፍል ላይ በተናጠል መተግበር ምቹ ነው.

ለኢንዛይም ምላሾች የፍጥነት እኩልታዎችን በሚያገኙበት ጊዜ ፣ ​​በርካታ ቀለል ያሉ ግምቶች ጥቅም ላይ ይውላሉ። በተለይም ፣ እንደ ደንቡ ፣ የኢንዛይም ምላሽ በጥሩ ድብልቅ ፣ የሙቀት መጠን እና ፒኤች ሁኔታ ውስጥ እንደሚሄድ ይገመታል ፣ እና ምላሹ በፍጥነት የኳሲ-ስቴሽን ሁኔታን ይመሰርታል (ክፍል 2.1 ይመልከቱ) ፣ ሁሉም መካከለኛ ዓይነቶች ኢንዛይም እርስ በርስ ሚዛናዊ ነው. "ኳሲ" የሚለው ቅድመ ቅጥያ ማለት ከተለዋዋጮች የተወሰነ ክፍል ብቻ ቋሚ እሴቶች ላይ ይደርሳል፣ የተቀረው ደግሞ ቀስ ብሎ መቀየሩን ይቀጥላል። የስብስቡ ክፍል (የባዮኬሚካላዊ ስርዓት) ወደ ኳሲ-ስቴሽናል እሴቶች ይደርሳል የሚለውን ግምት መጠቀም በሥነ ጽሑፍ ውስጥ የቦደንስታይን-ሴሜኖቭ ዘዴ በመባል ይታወቃል ። ይህ ዘዴ የባዮኬሚካላዊ ትንታኔን በሚያስደንቅ ሁኔታ ቀላል ለማድረግ ያስችልዎታል በምላሹ ወቅት የመካከለኛ ንጥረ ነገሮችን ለውጥ የሚገልጹ የመስመር ላይ ያልሆኑ ልዩነቶችን እኩልታዎች ስርዓቶችን ከመፍታት ይልቅ በዚህ ዘዴ መሠረት እርስ በእርስ የሚዛመዱ የአልጀብራ እኩልታዎች ስርዓቶችን ብቻ መፍታት ይችላሉ ።

የመካከለኛው ንጥረ ነገሮች ኳሲ-ስቴሽናል ክምችት። የኢንዛይም ምላሽ ውስጥ quasi-stationary ሁኔታ የተቋቋመበት ዋናው ምክንያት የኢንዛይም ትኩረት አብዛኛውን ጊዜ ኢንዛይም ጋር መስተጋብር substrates መካከል በማጎሪያ ያነሰ በርካታ ትዕዛዞች ነው.

በመካከለኛ ቅርጾች እና ውስብስቦች መካከል ያለው መስተጋብር በ monomolecular ምላሾች ስለሚወከለው እንደ ደንቡ ፣ የኢንዛይም ምላሾችን የquasi-statationary states የሚገልጹ የአልጀብራ እኩልታዎች ስርዓቶች መስመራዊ ናቸው። ስለዚህ የመስመራዊ አልጀብራ ዘዴዎች የመሃከለኛ ንጥረ ነገሮችን የኳሲ-ስታቴሽን ክምችት ለመወሰን ጥቅም ላይ ይውላሉ. ከቅርብ ዓመታት ወዲህ የግራፍ ንድፈ ሐሳብ ዘዴዎች ለዚህ ዓላማ በስፋት ጥቅም ላይ ውለዋል.

የኢንዛይም ምላሽ ግራፍ የሁሉም የኢንዛይም ውስብስቦች እና እነሱን የሚያገናኙት የተመሩ ቅርንጫፎች ፣ ከለውጡ ፍጥነት ቋሚ ጋር እኩል የሆነ እሴት ጋር የሚዛመዱ የአንጓዎች ስብስብ ነው። የዚህ ንጥረ ነገር ትኩረት በኳሲ-ስቴሽን ግዛት ውስጥ እንደ ቋሚነት ይቆጠራል.

ለምሳሌ, የኢንዛይም ምላሽ

በሁለት የኢንዛይም-ንዑስ ውስብስቶች መካከለኛ መፈጠር ውስጥ የሚፈሰው

ባለ ሶስት ኖዶች እና ስድስት የተመሩ ቅርንጫፎች ባለው ግራፍ በኳሲ-ስታቴሽን ግዛት ውስጥ ሊወከል ይችላል። አምድ (1.11) የቅርንጫፎቹን እሴቶች ያሳያል; ከመካከላቸው ሁለቱ የሚወሰኑት በኳሲ-ስቴሽነሪ ሁኔታ ውስጥ ቋሚ ናቸው ተብለው በሚታሰቡ ውህዶች ላይ ነው።

በመስቀለኛ መንገድ የሚመራ የግራፍ ዛፍ ከሁሉም የግራፍ ኖዶች ወደ መስቀለኛ መንገድ የሚመሩ ያልተዘጉ ቅርንጫፎች ስብስብ ነው። ዛፉ ምንም የተዘጉ ወይም ትይዩ ቅደም ተከተሎች የሉትም. የዛፍ ዋጋ የሁሉም ቅርንጫፎች እሴት ውጤት ነው። ለምሳሌ ፣ የግራፉ አንጓዎች (1.11) የሚከተሉት ዛፎች አሏቸው (እሴቶቻቸው ተሰጥተዋል)

(ስካን ይመልከቱ)

የመጀመሪያው ግራፍ ለስሌቶች አስፈላጊ የሆኑትን ሁሉንም መረጃዎች ስለሚይዝ, ዛፎችን በሚስሉበት ጊዜ, የመስቀለኛ መንገድ እና የቅርንጫፉ መጠኖች ምልክት በአብዛኛው ጥቅም ላይ አይውልም. ከዚህም በላይ አንድ የተወሰነ ክህሎት ሲደረስ የዛፎቹ መጠኖች ልክ እንደ መጀመሪያው ግራፍ - ዛፎችን ሳይሳቡ ይጻፋሉ.

ስብስቦች (ገጽ 24 ላይ) የመስቀለኛ መንገድ ዛፎች አይደሉም ምክንያቱም a የተዘጉ የቅርንጫፍ ቅደም ተከተል ነው (ዑደት)፣ ሁለት ትይዩ ቅርንጫፎች ያሉት ቅርንጫፎች የሚያገናኙት ኖዶች ያሉት ሲሆን ሐ ከ መስቀለኛ እስከ መስቀለኛ መንገድ ያለው ዑደት ከአንጓ ወደ መስቀለኛ መንገድ ያልተገናኘ ነው።

የመስቀለኛ መንገድ መሰረዣው ወደ መሰረታዊ መስቀለኛ መንገድ የሚመሩ የሁሉም ዛፎች እሴቶች ድምር ነው። የግራፍ ወሳኙ የሁሉም መሰረታዊ ግራፍ መወሰኛዎች ድምር ነው። ለምሳሌ የአንጓዎች እና በግራፍ (1.11) ውስጥ የሚወስኑት የሚከተሉት የዛፎች ድምር ናቸው (1.12)

(ስካን ይመልከቱ)

እና የዚህ ግራፍ ወሳኙ ከሶስት መሰረታዊ መወሰኛዎች ድምር ጋር እኩል ነው።

የኢንዛይም ምላሽ የመጀመሪያ ደረጃ ኳሲ-ስቴሽናል ፍጥነት የግብረ-መልስ ግራፍ በሚወስኑት አንፃር ይገለጻል ።

በመስቀለኛ መንገድ ምርቱን ለመመስረት ወይም ለማሰር የቋሚነት መጠን የመስቀለኛ ክፍል እና የኢንዛይም አጠቃላይ ትኩረትን የሚወስን ነው። ሊቀለበስ የሚችል ምርት በሚፈጠርበት ጊዜ የሚከተለው የምልክት ስምምነት ጥቅም ላይ ይውላል-መስቀለኛ መንገድ ምርቱን ከጣለ እና መስቀለኛ መንገድ ምርቱን ካሰረ።

ለምሳሌ, ለግራፍ (1.11) በቀመር (1.14) መሰረት አንድ ሰው መፃፍ አለበት

መበስበስ ነፃ ስለሚያወጣ፣ ሁለተኛው ቃል ደግሞ አሉታዊ ነው፣ ምክንያቱም በቁጥር ሰጪው ውስጥ ያለው የመጀመሪያው ቃል አዎንታዊ ነው።

የመካከለኛ ውስብስቦች የኳሲ-ስቴሽናል ውህዶች በቀመሩ ይገኛሉ

ስለዚህ, በአምድ (1.11) ውስጥ, የነጻ ኢንዛይም እና ውስብስቦች ስብስቦች በመግለጫዎች ይወሰናሉ