የተመራ እና ያልተመራ ግራፍ
አንድ ግራፍ ከቁመቶች እና ከጠርዞች ስብስብ የተሰራ የሂሳብ መዋቅር ነው። ግራፍ በአንዳንድ ማገናኛዎች (በጠርዞች የተወከለው) የተገናኙትን የነገሮች ስብስብ (በጫፍ የተወከለው) ይወክላል። ሒሳባዊ ምልክቶችን በመጠቀም ግራፍ በጂ ሊወከል ይችላል፣ G=(V፣ E) እና V የቋሚዎች ስብስብ ሲሆኑ ኢ ደግሞ የጠርዝ ስብስብ ነው። በማይመራው ግራፍ ውስጥ ጫፎቹን ከሚያገናኙት ጠርዞች ጋር የተያያዘ አቅጣጫ የለም. በተመራው ግራፍ ውስጥ ጫፎቹን ከሚያገናኙት ጠርዞች ጋር የተያያዘ አቅጣጫ አለ።
የማይመራ ግራፍ
ቀደም ሲል እንደተገለፀው ያልተመራ ግራፍ በግራፍ ውስጥ ያሉትን ጫፎች የሚያገናኙት በጠርዙ ውስጥ ምንም አቅጣጫ የሌለበት ግራፍ ነው።ምስል 1 ያልተመራውን ግራፍ ከቁመቶች ስብስብ ጋር ያሳያል V={V1, V2, V3}። ከላይ ባለው ግራፍ ላይ የጠርዝ ስብስብ እንደ V={(V1, V2), (V2, V3), (V1, V3)} ተብሎ ሊጻፍ ይችላል. በተጨማሪም ጠርዞቹ አቅጣጫ ስለሌላቸው የጠርዙን ስብስብ እንደ V={(V2, V1), (V3, V2), (V3, V1)} ለመጻፍ የሚከለክለው ምንም ነገር እንደሌለ ልብ ሊባል ይችላል. ስለዚህ ባልተመራው ግራፍ ውስጥ ያሉ ጠርዞች ጥንዶች የታዘዙ አይደሉም። ይህ ያልተመራ ግራፍ ዋና ባህሪ ነው. ያልተመሩ ግራፎች በማዕቀብ በሚወከሉ ነገሮች መካከል የተመጣጠነ ግንኙነትን ለመወከል ጥቅም ላይ ሊውሉ ይችላሉ። ለምሳሌ የከተሞችን ስብስብ የሚያገናኝ ባለሁለት መንገድ የመንገድ አውታር ያልተመራ ግራፍ በመጠቀም ሊወከል ይችላል። ከተሞቹ በግራፉ ላይ ባሉት ጫፎች ሊወከሉ የሚችሉ ሲሆን ጫፎቹ ደግሞ ከተማዎችን የሚያገናኙ ሁለት መንገድ መንገዶችን ይወክላሉ።
የተመራ ግራፍ
የተመራ ግራፍ በግራፉ ላይ ጫፎቹን የሚያገናኙበት ግራፍ ነው። ምስል 2 የ V={V1, V2, V3} ስብስብ ያለው ቀጥተኛ ግራፍ ያሳያል. ከላይ ባለው ግራፍ ላይ የጠርዝ ስብስብ እንደ V={(V1, V2), (V2, V3), (V1, V3)} ተብሎ ሊጻፍ ይችላል. ባልተመራው ግራፍ ውስጥ ያሉ ጠርዞች ጥንዶች የታዘዙ ናቸው። በመደበኛነት ፣ በተስተካከለ ግራፍ ውስጥ ያለው ጠርዝ ኢ በታዘዘው ጥንድ e=(x ፣ y) ሊወከል ይችላል ፣ x መነሻ ፣ ምንጭ ወይም የጠርዙ የመጀመሪያ ነጥብ ተብሎ የሚጠራው ነው ፣ እና vertex y ተብሎ የሚጠራው ተርሚነስ ነው, ማለቂያ ጫፍ ወይም ተርሚናል ነጥብ. ለምሳሌ አንድ መንገድ መንገዶችን በመጠቀም የከተማዎችን ስብስብ የሚያገናኝ የመንገድ አውታር ያልተመራ ግራፍ በመጠቀም ሊወከል ይችላል። ከተማዎቹ በግራፉ ውስጥ ባሉ ጫፎች ሊወከሉ ይችላሉ እና የተመሩ ጠርዞች የትራፊክ ፍሰት በመንገዱ ላይ ያለውን አቅጣጫ ግምት ውስጥ በማስገባት ከተሞችን የሚያገናኙ መንገዶችን ያመለክታሉ.
በDirected Graph እና Undirected Graph መካከል ያለው ልዩነት ምንድን ነው?
በቀጥታ ግራፍ ውስጥ አንድ ጠርዝ የታዘዘ ጥንድ ነው፣እዚያም የታዘዙት ጥንድ ሁለቱን ጫፎች የሚያገናኘውን የጠርዝ አቅጣጫ ይወክላሉ። በሌላ በኩል, ባልተመራው ግራፍ ውስጥ, ጠርዝ ከጠርዝ ጋር የተያያዘ ምንም አይነት አቅጣጫ ስለሌለ, ያልታዘዘ ጥንድ ነው. ያልተመሩ ግራፎች በነገሮች መካከል ያለውን የተመጣጠነ ግንኙነት ለመወከል ጥቅም ላይ ሊውሉ ይችላሉ። በማይመራው ግራፍ ውስጥ ያለው እያንዳንዱ መስቀለኛ ክፍል በዲግሪ እና በዲግሪ እኩል ነው ነገር ግን ይህ ለተመራ ግራፍ እውነት አይደለም። ያልተመራውን ግራፍ ለመወከል ማትሪክስ ሲጠቀሙ፣ ማትሪክስ ሁልጊዜ ሲሜትሪክ ግራፍ ይሆናል፣ ነገር ግን ይህ ለተመሩ ግራፎች እውነት አይደለም። እያንዳንዱን ጠርዝ በተቃራኒ አቅጣጫ በሚሄዱ ሁለት የተመሩ ጠርዞች በመተካት ያልተመራ ግራፍ ወደ ቀጥታ ግራፍ መቀየር ይቻላል. ነገር ግን፣ የተመራውን ግራፍ ወደ ወዳልተመራው ግራፍ መቀየር አይቻልም።
