رسم بياني للصداقة

في مجال نظرية المخططات الرياضية ، فإن مخطط الصداقة (أو مخطط طاحونة الهواء الهولندي أو مخطط المروحة من الرتبة n ) F _n هو مخطط مستوٍ وغير موجه يحتوي على 2 n + 1 رأس و 3 n حافة. ^{​​[ 1 ]}

يمكن إنشاء مخطط الصداقة F _n عن طريق ضم n نسخة من مخطط الدورة C ₃ برأس مشترك، والذي يصبح رأسًا عامًا للمخطط. ^{[ 2 ]}

بحسب التصميم، فإن مخطط الصداقة F_{_n} متماثل مع مخطط طاحونة الهواء Wd(3, n ) . وهو مخطط ذو مسافة وحدة ، محيطه 3، وقطره 2، ونصف قطره 1. أما المخطط F_₂ فهو متماثل مع مخطط الفراشة . وتُعمم مخططات الصداقة بواسطة مخططات الصبار المثلثية .

تنص نظرية الصداقة لبول إيردوس ، وألفريد ريني ، وفيرا تي . سوس ( 1966 ) ^{[ 3 ]} على أن الرسوم البيانية المحدودة التي تتميز بخاصية وجود جار واحد مشترك بين كل رأسين فيها هي تحديدًا رسوم بيانية للصداقة. بعبارة أخرى، إذا كانت مجموعة من الأشخاص تتميز بخاصية وجود صديق مشترك واحد بين كل زوج منهم، فلا بد من وجود شخص واحد صديق لجميع الآخرين. مع ذلك، بالنسبة للرسوم البيانية غير المحدودة، قد توجد رسوم بيانية مختلفة كثيرة لها نفس العدد من العناصر وتتمتع بهذه الخاصية. ^{[ 4 ]} 

قدّم ميرتزيوس وأونغر برهانًا توافقيًا لنظرية الصداقة. ^{[ 5 ]} وقدّم كريغ هونيك برهانًا آخر . ^{[ 6 ]} ونشر ألكسندر فان دير فيكنز برهانًا رسميًا في ميتاماث في أكتوبر 2018 على القائمة البريدية لميتاماث. ^{[ 7 ]}

يمتلك مخطط الصداقة عددًا لونيًا 3 ومؤشرًا لونيًا 2n . ويمكن استنتاج متعدد الحدود اللوني الخاص _به من متعدد الحدود اللوني لمخطط الدورة C3 ، وهو يساوي

${\displaystyle (x-2)^{n}(x-1)^{n}x}$.

تكون شبكة الصداقة F_{_n} ذات حواف أنيقة إذا وفقط إذا كان n عددًا فرديًا. وتكون أنيقة إذا وفقط إذا كان n ≡ 0 (mod 4) أو n ≡ 1 (mod 4) . ^{[ 8 ] [ 9 ]}

كل رسم بياني للصداقة هو عامل حاسم .

وفقًا لنظرية الرسم البياني المتطرفة ، يجب أن يحتوي كل رسم بياني يحتوي على عدد كافٍ من الحواف (مقارنةً بعدد رؤوسه) على${\displaystyle k}$-fan كرسم بياني فرعي. وبشكل أكثر تحديدًا، ينطبق هذا على${\displaystyle n}$الرسم البياني ذو الرؤوس (لـ${\displaystyle n}$كبيرة بما يكفي من حيث${\displaystyle k}$) إذا كان عدد الحواف

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}$

أين${\displaystyle f(k)}$يكون${\displaystyle k^{2}-k}$لو${\displaystyle k}$غريب، و ${\displaystyle f(k)}$يكون${\displaystyle k^{2}-3k/2}$لو${\displaystyle k}$وهي زوجية. تعمم هذه الحدود نظرية توران حول عدد الحواف في الرسم البياني الخالي من المثلثات ، وهي أفضل الحدود الممكنة لهذه المسألة (عندما${\displaystyle n\geq 50k^{2}}$)، بمعنى أنه لأي عدد أقل من الحواف، توجد رسوم بيانية لا تحتوي على${\displaystyle k}$-fan. ^{[ 10 ]}

أي رأسين لهما جار واحد مشترك يكافئ أي رأسين متصلين بمسار واحد فقط طوله اثنان. وقد تم تعميم هذا إلى${\displaystyle P_{k}}$الرسوم البيانية -، حيث يتم توصيل أي رأسين بمسار فريد طوله${\displaystyle k}$. ل${\displaystyle k\geq 3}$لا توجد مثل هذه الرسوم البيانية المعروفة، والادعاء بعدم وجودها هو تخمين كوتزيج .

• الرسم البياني المركزي الموجه ، هو رسم بياني موجه يتميز بخاصية إمكانية ربط كل رأسين فيه بمسار فريد من حافتين.