מספר הגרפים הפשוטים, שאינם מכוונים, עם n צמתים שונים בהם אין צמתים מבודדים?

שלום, אני מנסה למצוא את מספר הגרפים הפשוטים, שאינם מכוונים, עם n צמתים שונים בהם אין צמתים מבודדים?
אני חושב שצריך לפתור את השאלה בעזרת עקרון הכלה והפרדה אבל אני לא בטוח איזה תכונות להגדיר.

היי גלעד,
אכן צריך להשתמש בעקרון הכלה והפרדה כדי לפתור את השאלה.

עולם - כל הגרפים הפשוטים, שאינם מכוונים, עם n צמתים שונים. גרף פשוט הינו גרף ללא לולאות עצמאיות וללא קשתות מקבילות. כמו כן, בגרף מכוון, כל קשת היא זוג סדור של צמתים. ע"פ שתי ההגדרות הנ"ל, נוכל להסיק כי כל קשת הנמצאת בגרף פשוט, אשר אינו מכוון, הינה חיבור בין שני צמתים (שונים). אין חשיבות לסדר ואין חזרות בקשת ולכן קיימים {n \choose 2} אפשרויות למקם את הקשת. עתה, ישנן שתי אפשרויות - לשים את הקשת או לא. לפיכך נוכל להסיק כי קיימים 2^{{n \choose 2}} גרפים פשוטים, לא מכוונים, עם n צמתים שונים, כלומר מתקיים:

W(0)=2^{{n \choose 2}}

תכונות - יהיו n תכונות רעות כאשר משמעות התכונה P_{i} (לכל 1\leq i\leq n) היא שצומת m_{i} מבודד, כלומר אין אף קשת בין צומת זה לבין כל שאר הצמתים.

יעד - מאחר ומדובר בתכונות רעות, עלינו למצוא את E(0):
אם תכונה P_{i} מתקיימת, הרי שצומת m_{i} מבודד. לכן עלינו לסדר את שאר n-1 הצמתים בגרף פשוט לא מכוון. בדומה לאיך שמצאנו את העולם, מספר האפשרויות למקם כל קשת: {n-1 \choose 2}. עתה לכל אחת מהקשתות יש שתי אפשרויות - לשים את הקשת או לא. לפיכך, נוכל להסיק כי מתקיים:

\forall i\in[1,n],\,W(p_{i})=2^{{n-1 \choose 2}}\Rightarrow W(1)=\sum_{i=1}^{n}W(p_{i})={n \choose 1}\cdot 2^{^{{n-1 \choose 2}}}

עתה, נניח כי r תכונות רעות מתקיימות, כלומר יש r צמתים מבודדים. לכן נותר לסדר את שאר n-r הצמתים בגרף פשוט לא מכוון. בדומה לאיך שחישבנו את העולם, מספר האפשרויות למקם כל קשת: {n-r \choose 2} כך שלכל אחת מהקשתות שתי אפשרויות (לשים את הקשת או לא). לפיכך, נוכל להסיק כי מתקיים:

\forall r\in[1,n],\,W(p_{1},...,p_{r})=2^{{n-r \choose 2}}\Rightarrow W(r)={n \choose r}\cdot 2^{{n-r \choose 2}}

אי-לכך, נוכל להסיק ע"פ הנוסחה:

E(0)=\sum_{r=0}^{n}(-1)^{r}\cdot W(r)=\sum_{r=0}^{n}(-1)^{r}\cdot{n \choose r}\cdot 2^{{n-r \choose 2}}
לייק 1