رسم بياني غريب

إذا كان هناك رأسان في${\displaystyle O_{n}}$تتوافق مع مجموعات تختلف عن بعضها البعض بإزالة${\displaystyle k}$عناصر من مجموعة واحدة وإضافة${\displaystyle k}$عناصر مختلفة، ثم يمكن الوصول إليها من بعضها البعض في${\displaystyle 2k}$خطوات، كل زوج منها يقوم بعملية جمع وطرح واحدة. إذا${\displaystyle 2k<n}$هذا هو أقصر مسار ؛ وإلا، فسيكون من الأقصر إيجاد مسار من هذا النوع من المجموعة الأولى إلى مجموعة مكملة للمجموعة الثانية، ثم الوصول إلى المجموعة الثانية في خطوة إضافية. لذلك، فإن قطر${\displaystyle O_{n}}$يكون${\displaystyle n-1}$[ ^{1 ] [ 2 ]​}

كل رسم بياني فردي هو رسم بياني متعدٍّ على ثلاثة أقواس : أي مسار موجه بثلاثة حواف في رسم بياني فردي يمكن تحويله إلى أي مسار آخر مماثل بفضل تناظر الرسم البياني. ^{[ 12 ]} الرسوم البيانية الفردية متعدية على المسافة ، وبالتالي فهي منتظمة المسافة . ^{[ 2 ]} وبصفتها رسومًا بيانية منتظمة المسافة، فإنها تُعرَّف بشكل فريد من خلال مصفوفة تقاطعها: لا يمكن لأي رسوم بيانية منتظمة المسافة أخرى أن تمتلك نفس معلمات الرسم البياني الفردي. ^{[ 13 ]} ومع ذلك، على الرغم من درجة تناظرها العالية، فإن الرسوم البيانية الفردية${\displaystyle O_{n}}$ل${\displaystyle n>2}$لا تُعتبر أبدًا رسومًا بيانية لكايلي . ^{[ 14 ]}

لأن الرسوم البيانية الفردية منتظمة ومتعدية الحواف ، فإن اتصال رؤوسها يساوي درجتها.${\displaystyle n}$[ ^{15 ]​}

رسوم بيانية غريبة مع${\displaystyle n>3}$يبلغ محيطها ستة؛ ومع ذلك، على الرغم من أنها ليست رسومًا بيانية ثنائية الأجزاء ، فإن دوراتها الفردية أطول بكثير. على وجه التحديد، الرسم البياني الفردي${\displaystyle O_{n}}$له محيط غريب${\displaystyle 2n-1}$إذا${\displaystyle n}$- الرسم البياني المنتظم له قطر${\displaystyle n-1}$ومحيط غريب${\displaystyle 2n-1}$وليس لديه سوى${\displaystyle n}$إذا كانت القيم الذاتية مميزة ، فلا بد أن يكون الرسم البياني منتظم المسافة. الرسوم البيانية المنتظمة المسافة ذات القطر${\displaystyle n-1}$ومحيط غريب${\displaystyle 2n-1}$تُعرف هذه الرسوم البيانية باسم الرسوم البيانية الفردية المعممة ، وتشمل الرسوم البيانية المكعبة المطوية بالإضافة إلى الرسوم البيانية الفردية نفسها. ^{[ 4 ]}

يترك${\displaystyle O_{n}}$ليكن رسمًا بيانيًا فرديًا معرفًا من مجموعات جزئية من${\displaystyle (2n-1)}$مجموعة العناصر${\displaystyle X}$ودع${\displaystyle x}$أن يكون أي عضو في${\displaystyle X}$ثم، من بين رؤوس${\displaystyle O_{n}}$، بالضبط${\displaystyle {\tbinom {2n-2}{n-2}}}$تتوافق الرؤوس مع المجموعات التي تحتوي${\displaystyle x}$لأن جميع هذه المجموعات تحتوي على${\displaystyle x}$فهي ليست منفصلة، ​​وتشكل مجموعة مستقلة من${\displaystyle O_{n}}$. إنه،${\displaystyle O_{n}}$لديه${\displaystyle 2n-1}$مجموعات مستقلة مختلفة من الحجم${\displaystyle {\tbinom {2n-2}{n-2}}}$ويترتب على ذلك من نظرية إردوش-كو-رادو أن هذه هي المجموعات المستقلة القصوى لـ${\displaystyle O_{n}}$أي عدد الاستقلال لـ${\displaystyle O_{n}}$يكون${\displaystyle {\tbinom {2n-2}{n-2}}.}$علاوة على ذلك، يجب أن يكون لكل مجموعة مستقلة قصوى هذا الشكل، لذلك${\displaystyle O_{n}}$يحتوي بالضبط${\displaystyle 2n-1}$أكبر مجموعات مستقلة. ^{[ 2 ]}

لو${\displaystyle I}$هي مجموعة مستقلة قصوى، تتكون من المجموعات التي تحتوي${\displaystyle x}$ثم مكمل لـ${\displaystyle I}$هي مجموعة الرؤوس التي لا تحتوي على${\displaystyle x}$تُحفز هذه المجموعة التكميلية عملية مطابقة في${\displaystyle G}$كل رأس من رؤوس المجموعة المستقلة مجاور لـ${\displaystyle n}$رؤوس المطابقة، وكل رأس من رؤوس المطابقة مجاور لـ${\displaystyle n-1}$رؤوس المجموعة المستقلة. ^{[ 2 ]} بسبب هذا التفكيك، ولأن الرسوم البيانية الفردية ليست ثنائية الأجزاء، فإن لها عددًا لونيًا ثلاثة: يمكن تعيين لون واحد لرؤوس المجموعة المستقلة القصوى، ويكفي لونان إضافيان لتلوين المطابقة التكميلية.

بحسب نظرية فيزينغ ، فإن عدد الألوان اللازمة لتلوين حواف الرسم البياني الفردي${\displaystyle O_{n}}$إما${\displaystyle n}$أو${\displaystyle n+1}$وفي حالة الرسم البياني لبيترسن${\displaystyle O_{3}}$إنها${\displaystyle n+1}$. متى${\displaystyle n}$بما أن قوة للعدد اثنين ، فإن عدد رؤوس الرسم البياني فردي، ومن ثم يتبين أن عدد ألوان الحواف هو${\displaystyle n+1}$[ ^{16 ]} ومع ذلك ^،${\displaystyle O_{5}}$،${\displaystyle O_{6}}$، و${\displaystyle O_{7}}$يمكن تلوين حواف كل منها بـ${\displaystyle n}$الألوان. ^{[ 2 ] [ 16 ]}

يشرح بيغز ^{[ 9 ]} هذه المشكلة من خلال القصة التالية، عن "لاعبي كرة القدم في كروم": أحد عشر لاعب كرة قدم في بلدة كروم الخيالية يرغبون في تشكيل فرق ثنائية من خمسة لاعبين (مع لاعب واحد ليكون حكمًا) بجميع الطرق الممكنة البالغ عددها 1386 طريقة، ويرغبون في جدولة المباريات بين كل ثنائي بحيث تُلعب المباريات الست لكل فريق في ستة أيام مختلفة من الأسبوع، مع يوم الأحد عطلة لجميع الفرق. هل من الممكن فعل ذلك؟ في هذه القصة، تمثل كل مباراة حافة من${\displaystyle O_{6}}$يُمثل كل يوم من أيام الأسبوع بلون، ويتم تلوين الحواف بستة ألوان.${\displaystyle O_{6}}$يوفر حلاً لمشكلة جدولة اللاعبين.

رسم بياني لبيترسن${\displaystyle O_{3}}$هو رسم بياني غير هاميلتوني معروف ، ولكن جميع الرسوم البيانية الفردية${\displaystyle O_{n}}$ل${\displaystyle n\geq 4}$من المعروف أن لها دورة هاميلتونية . ^{[ 17 ]} وبما أن الرسوم البيانية الفردية متعدية الرؤوس ، فإنها بالتالي تُعد إحدى الحالات الخاصة التي لها إجابة إيجابية معروفة لتخمين لوفاس حول الدورات الهاميلتونية في الرسوم البيانية متعدية الرؤوس. وقد خمّن بيغز ^{[ 2 ]} بشكل أعم أن حواف${\displaystyle O_{n}}$يمكن تقسيمها إلى${\displaystyle \lfloor n/2\rfloor }$دورات هاميلتونية منفصلة الحواف. عندما${\displaystyle n}$إذا كان العدد فرديًا، فلا بد أن تشكل الحواف المتبقية تطابقًا تامًا. وقد تم التحقق من هذه الفرضية الأقوى لـ${\displaystyle n=4,5,6,7}$[ ^{2 ] [ 16 ]} لـ^​${\displaystyle n=8}$، عدد الرؤوس الفردي في${\displaystyle O_{n}}$يمنع وجود تلوين حواف بثمانية ألوان، ولكنه لا يستبعد إمكانية التقسيم إلى أربع دورات هاميلتونية.