የሁለትዮሽ ግራፍ ተገናኝቷል?
የሁለትዮሽ ግራፍ ተገናኝቷል?
Anonim

1 መልስ። የተገናኘ የሁለትዮሽ ግራፍ ነው ሀ ግራፍ ሁለቱን ማሟላት፣ የሚከተሉት ሁኔታዎች፡- ጫፎች በሁለት የተከፋፈሉ U እና V ስብስቦች ሊከፈሉ ይችላሉ (ማለትም፣ U እና V እያንዳንዱ ገለልተኛ ስብስቦች ናቸው) ግራፍ ያገናኛል በ U ወደ አንድ በቪ.

በተመሳሳይ መልኩ አንድ ሰው ግራፍ ባለ ሁለትዮሽ መሆኑን እንዴት ያውቃሉ?

ስለዚህ ከሆነ ቀለምዎን 2 ቀለም ማድረግ ይችላሉ ግራፍ, ይሆናል የሁለትዮሽ. በግልጽ፣ ከሆነ ትሪያንግል አለህ፣ ለቀለም 3 ቀለማት ያስፈልግሃል። መቼ ባለ2-ቀለም አለህ፣ ሁለቱ የቀለም ክፍሎች (ቀይ ጫፎች፣ ሰማያዊ ጫፎች)፣ ሁለትዮሽ ይሰጡሃል። ሀ ግራፍ bipartite ከሆነ እና ብቻ ከሆነ በ ውስጥ ያልተለመደ ዑደት የለም ግራፍ.

በተጨማሪም፣ እያንዳንዱ ዛፍ የሁለትዮሽ ግራፍ ነው? በ 2 ጫፎች መካከል ልዩ የሆነ መንገድ አለ ዛፍ. እያንዳንዱ ዛፍ ቢያንስ 2 ጫፎች ያሉት የዲግሪ 1 ቢያንስ 2 ጫፎች አሉት። እያንዳንዱ ዛፍ ነው። የሁለትዮሽ. ማንኛውንም ጠርዝ ከ ሀ ዛፍ የሚለውን ይለያል ዛፍ ወደ 2 የተገናኙ አካላት.

ከዚህ ጎን ለጎን ግራፍ ሁለትዮሽ መሆን ማለት ምን ማለት ነው?

በሂሳብ መስክ የ ግራፍ ቲዎሪ፣ ሀ የሁለትዮሽ ግራፍ (ወይም ቢግራፍ) ሀ ግራፍ የማን ጫፎች በሁለት የተከፋፈሉ እና ገለልተኛ ስብስቦች ሊከፈሉ የሚችሉ እና እያንዳንዱ ጠርዝ አንድን ወርድ ከአንዱ ጋር ያገናኛል። የቬርቴክስ ስብስቦች እና. ብዙውን ጊዜ የአካል ክፍሎች ይባላሉ ግራፍ.

በሁለትዮሽ ግራፍ እና ሙሉ ባለሁለት ግራፍ መካከል ያለው ልዩነት ምንድን ነው?

የሁለትዮሽ ግራፍ G የሁለት ጫፎች ስብስብ A እና B ያለው ሲሆን በጂ ውስጥ ያሉት ሁሉም ጠርዞች አንድ ጫፍ አላቸው. በ A እና በ B.G ውስጥ አንድ ጫፍ ተጠናቀቀ ከ A እስከ B ያለው እያንዳንዱ ጠርዝ ከሆነ በግራፍ ውስጥ. የ ልዩነት ነው። በውስጡ "ሁሉም" የሚለው ቃል.

በርዕስ ታዋቂ