יום שני, 12 באוגוסט 2019

מתמטיקה בדידה קומבינטוריקה האוניברסיטה הפתוחה רמה אוניברסיטאית

קומבינטוריקה כפי שהיא נלמדת בשיעורים של האוניברסיטה הפתוחה

תמורות ללא חזרות
כמה אפשרויות יש לסדר n עצמים שונים בשורה?
התשובה היא: 

n!

כמה יחסי סדר מלא יש מעל קבוצת בת n איברים? התשובה היא !n



תמורות עם חזרות
כמה אפשרויות יש לסדר n עצמים, לא בהכרח שונים, בשורה.
(מחלקים את העצמים לקבוצות, כל סדרה / אוסף של עצמים שלא ניתן להבדיל ביניהם יהיו סוג, נניח k סוגים).
כמו שאמרנו מחלקים את העמים ל-k סוגים שונים.
נסמן ב n1 את מספר העצמים מסוג 1.
נסמן ב n2 את מספר העצמים מסוג 2.
נסמן ב nk את מספר העצמים מסוג k.
העצמים מאותו הסוג נחשבים זהים.

עצמים מסוגים שונים נחשבים שונים.

פתרון:

(n!)/(n1!n2!n3!...nk!)

בכמה אופנים ניתן לסדר בשורה את הספרות של המספר:
11214337
כמו שניתן לראות ניתן להבחין בחמישה סוגים:
סוג הסיפרה 1: יש 3
סוג הסיפרה 2: יש 1
סוג הסיפרה 4: יש 1
סוג הסיפרה 3: יש 2
סוג הסיפרה 7: יש 1
הסכום של כולם הוא:  8
(8!)/(3!1!1!2!1!)=(8!)/(3!2!)

בכמה מבין הסידורים בשאלה הקודמת לא מופיע הרצף 33?

פתרון: על מנת לחשב את מספר הסידורים בהם לא מופיע הרצף 33, נחשב תחילה מהו מספר הסידורים שבהם כן מופיע הרצף 33, ופשוט נחסר את האופציה הזאת ממספר הסידורים האפשרי.
11214(33)7

(נחשיב את הרצף 33 כמישהו אחד, כ-סיפרה בפני עצמה)
כמו שניתן לראות ניתן להבחין בחמישה סוגים:
סוג הסיפרה 1: יש 3
סוג הסיפרה 2: יש 1
סוג הסיפרה 4: יש 1
סוג הסיפרה 33: יש 1
סוג הסיפרה 7: יש 1
הסכום של כולם הוא:  7
(7!)/(3!1!1!1!1!)=(7!)/(3!)

בשאר הסידורים 33 אינו מופיע כרצף, ומספר זה הוא:
(8!)/(3!2!)-(7!)/(3!)


חליפות בלי חזרות
מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, בלי חזרות ועם חשיבות לסדר הבחירה.
פתרון:
n(n-1)(n-2)(n-3)...(n-k+1)
המספר הזה מסומן כ:
p(n,k)
שימו לב שאם k>0 אז p(n,k)=0
אם k<n או k=n אז:
 p(n,k)=(n!)/(n-k)!



שאלה: כמה פונקציות חד חד ערכיות (חח"ע) יש מהקבוצה:
A={1,2,3,4}
לקבוצה
B={5,6,7,8,9,10}
פתרון:
אנו מתבקשים לבחור 4 איברים שונים מ-B עם חשיבות מי ייבחר למי, כלומר עם חשיבות לסדר.
k=4
n=6
p(n,k)=(n!)/(n-k)!
p(6,4)=(6!)/(2)!


חליפות עם חזרות
מספר האפשרויות לבחור k עצמים מתוך n עצמים, מותר לבצע חזרות בבחירה ויש חשיבות לסדר.
פתרון:
n*n*n*n*n...*n=n^k

מספר הפונקציות מ-A ל-B, ללא דרישת חד חד ערכיות (חח"ע) או דרישות אחרות.
A={1,2,3,4}
B={5,6,7,8,9,10}
פתרון: 
k=4
n=6
n^k
6^4

צירופים בלי חזרות
מספר האפשרויות לבחור k עצמים מתוך n עצמים שונים, בלי חזרות וללא חשיבות לסדר הבחירה.
פתרון:
מסמנים את זה n מעל k בסוגריים גדולות: {n \choose k} שזה שווה ל:
(p(n,k))/(k!)
כאשר k>n:
(p(n,k))/(k!)=0

כאשר k<n או k=n:

(p(n,k))/(k!)=(n!)(k!(n-k)!)

כמה אפשרויות יש לבחירת תת קבוצה בת k איברים מתוך קבוצה בת n איברים?
פתרון
{n \choose k}



שאלה: נתונות הספרות 1,2,3,4,5 והאותיות a,b,c,d,e,f
1. מהו מספר האפשרויות לסדר את הסימנים הללו בשורה ללא כל הגבלה.

תשובה לשאלה מספר 1:
הריי שמדובר בתמורות ללא חזרות (כולם שונים, חזרות לא יכולות להתקיים ואין חשיבות לסדר).
11!

2. מתוך האפשרויות של שאלה מספר 1, בכמה אפשרויות 1,2 אינן סמוכות?

תשובה לשאלה מספר 2:
נחשב תחילה בכמה מהאפשרויות 1,2 סמוכות ואז נחסיר מ- !11.

נחלק את השאלה לכמה חלקים:
בכמה אפשרויות הרצף 12 מופיע?
כאמור עכשיו יש לנו 10 עצמים ולא 11, כלומר מספר האפשרויות שזה יקרה הוא !10

בכמה אפשרויות הרצף 21 מופיע?
אותו הסבר בדיוק, !10

וביחד:
10!+10!=2*10!

מספר האפשרויות שבו מספר הספרות 1,2 אינן סמוכות, מתוך מספר האפשרויות שיצא בשאלה אחת הוא:
11!-2-10!


3. מתוך האפשרויות של 1, בכמה אפשרויות 1 איננו סמוך לשום סיפרה?

תשובה לשאלה מספר 3:
נפריד לשלוש מקרים זרים:
א. בראש השורה:
1_ _ _ _ _ _ _ _ _ _

במיקום הראשון 1 יופיע
במיקום השני חייבת להופיע סיפרה כלשהי, יש לנו 6 ספרות, זאת אומרת יש לנו 6 אפשרויות!

עד עכשיו יש לנו את הסיפרה אחת, ואות כלשהי, זאת אומרת נותר למלא את כל השאר (התחלנו עם 5 מספרים נותרנו עם 4 מספרים, התחלנו עם התחלנו עם 6 אותיות נותרנו עם 5 אותיות) בסך הכל יש לנו 4+5=9, 9 עצמים, וכמו מקודם מדובר בתמורות ללא חזרות: !9

התשובה לחלק א'
6*9!


ב. 1 בסוף השורה, מטעמיי סימטריה:

6*9!

ג. 1 איננו בקצוות, נבצע תהליך בן שלושה שלבים:
ג1. נבחר אות שתהיה לפני 1 (יש לנו 6 אותיות, לכן 6 אפשרויות): 6
ג2. נבחר אות שתהיה אחרי 1 (יש לנו 5 אותיות, לכן 5 אפשרויות: 5
בעצם עצם בעל 3 סימנים
ג3. נסדר עצם זה בשורה עם על הסימנים שנותרו: כעת יש לנו 9 עצמים (עצם אחד: _1_ (לפני ואחרי יש אות), 4 ספרות שנשארו, ו-4 אותיות שנשארו. זאת אומרת סה"כ נשארו 9 עצמים (כולם שונים, ללא חזרות, לא משנה הסדר): !9
סה"כ:
6*5*9!=30*9!

נסכם את האפשרויות

2*6*9!+30*9!=42*9!

4. מתוך האפשרויות של שאלה 1, בכמה אפשרויות אין בכלל ספרות סמוכות.
תשובה לשאלה 4:
בשלב הראשון יש לסדר את 6 האותיות בשורה (כולם שונים, ללא חזרות, לא משנה הסדר), זה תמורות ללא חזרות, לכן זה !6

נניח בחרנו את הופעת האותיות כך:
_a_b_c_d_e_f_
הריי שיש לנו 7 מקומות חסרים, שצריך למלא אותם במספרים.
יש לנו 5 ספרות. כולם שונים, ללא חזרות ויש חשיבות לסדר: חליפות בלי חזרות.

k=5
n=7
 p(n,k)=(n!)/(n-k)!
 p(7,5)=(7!)/(2!)


תשובה סופית
6!*(7!/2!)


צירופים עם חזרות
בכמה אפשרויות אפשר לבחור k עצמים מתוך n עצמים שונים, עם אפשרות לחזרות ובלי חשיבות לסדר?
פתרון:
D(n,k)=(n+k-1)!/(k!(n-1)!)


שאלה:
בכמה אפשרויות ניתן לבחור 10 כדורים, ללא חשיבות לסדר הבחירה מתוך:
9 אדומים
8 צהובים
7 לבנים
כדורים מאותו צבע נחשבים זהים.

אם לא היית הגבלה על מספר הכדורים מכל צבע, אז התנאים שהיו מתקיימים: לא כולם שונים, עם חזרות, אין חשיבות לסדר, אנחנו צריכים לבחור 10 כדורים מתוך שלושה צבעים לכן:
n=3
k=10
D(n,k)=(n+k-1)!/(k!(n-1)!)
D(3,10)=(12)!/(10!(2)!)=66
התוצאה התקבלה מהצבה במחשבון.

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

לבן (קיימים 7)
צהוב (קיימים 8)
אדום  (קיימים 9)
0
00
10
0
10
0
0
9
1
1
9
0
10
0
0
9
0
1
9
1
0
8
2
0
8
1
1
8
0
2

סך הכל יש לנו 10 אופציות שנפסלות, לא יכולות להתקיים.

אז התשובה היא
 66-10=56



נשדרג את השאלה, נוסיף את הדרישה: חייבים לבחור כדור אחד מכל צבע.

תשובה: איך זה משפיע עלינו?
אנחנו חייבים לבחור כדור אחד אדום (במקום 9 כדורים אדומים יש לנו עכשיו 8), חייבים לבחור כדור צהוב (במקום 8 צהובים נותרנו עם 7), וחייבים לבחור כדור לבן (במקום 7 לבנים נותרנו עם 6).

זאת אומרת אנחנו צריכים לבחור עוד 7 כדורים מתוך 3 צבעים שנותרו
(לא כולם שונים, עם חזרות, אין חשיבות לסדר: צירופים עם חזרות), ללא הגבלה על החזרות:
n=3
k=7
D(n,k)=(n+k-1)!/(k!(n-1)!)
D(3,7)=(9)!/(7!(2)!)=36

צריך לפסול את מה שלא יכול להתקיים
לבן (קיימים 6)
צהוב (קיימים 7)
אדום  (קיימים 8)
7
0
0

זאת האופציה היחידה שלא יכולה להתקיים, לכן התשובה היא:
36-1=35


תרגיל:
נתונה המשוואה:
x1+x2+...+xn=k
כאשר n,k מספרים טבעיים.
כמה פתרונות יש למשוואה הזו במספרים טבעיים [כולל אפס].

תשובה: לא כולם שונים, עם חזרות, ואין חשיבות לסדר, לכן מדובר פה בצירופים עם חזרות:
D(n,k)

כמה פתרונות יש למשוואה:
x1+x2+x3+x4=30
1. כאשר כל המשתנים טבעיים וזוגיים.

פתרון לשאלה 1:
נציב:
x1=2y1, x2=2y2, x3=2y3, x4=2y4
yi טבעי כלשהו אם ורק אם x1 טבעי זוגי כלשהו

אחרי ההצבה נקבל:

2y1+2y2+2y3+2y4=30
y1+y2+y3+y4=15

צריך את מספר הפתרונות הטבעיים כלשהם למשוואה הזו (לא כולם שונים,  עם חזרות, אין חשיבות לסדר) נשתמש בצירופים עם חזרות:

אנחנו צריכים לבחור 15 עצמים מתוך 4 טבעיים (כמו בשאלה הקודמת, צריך לבחור 10 כדורים מתוך 3 צבעים):
n=4
k=15
D(n,k)=(n+k-1)!/(k!(n-1)!)
D(4,15)=(18)!/(15!(3)!)=816
(החישוב בוצע על ידי מחשבון).


2. כאשר כל המשתנים טבעיים ואי זוגיים
פתרון שאלה 2:
נציב:
x1=2y1+1 , x2=2y2+1, x3=2y3+1, x4=2y4+1
ואז נקבל:
2y1+1+2y2+1+2y3+1+2y4+1=30
2y1+2y2+2y3+2y4=30-4
2y1+2y2+2y3+2y4=26
y1+y2+y3+y4=13
אנחנו צריכים לבחור 13 עצמים מתוך 4 טבעיים (כמו בשאלה הקודמת, צריך לבחור 10 כדורים מתוך 3 צבעים):
n=4
k=13
D(4,13)=(16)!/(13!(3)!)=560

3. כאשר שניים מהמשתנים [לא משנה איזה] הם זוגיים ואילו השניים האחרים אי זוגיים.

פתרון לשאלה 3:
נפתור תחילה עבור:
x1,x2 זוגיים
x3,x4 אי זוגיים
נחשב את כל האופציות שבהן אפשר לבחור מי יהיה זוגי ומי אי זוגי מבין הארבעה:
זאת אומרת אנחנו צריכים לבחור 2 אי זוגיים מתוך 4 אפשרויות (אם יש 2 אי זוגיים, זה אומר שהשניים האחרים הם אי זוגיים כי אלו האפשרויות שלנו), כולם שונים, ללא חזרות, אי חשיבות לסדר (צריך לבחור 2 מתוך 4): צירופים בלי חזרות
k=2
n=4
(p(n,k))/(k!)
(p(4,2))/(2!)=(4!)/(2!(2)!)=6

נכפיל את התוצאה ב-6.

נציב:
x1=2y1
x2=2y2
x3=2y3+1
x4=2y4+1

2y1+2y2+2y3+1+2y4+1=30
2y1+2y2+2y3+2y4=28
y1+y2+y3+y4=14

אנחנו צריכים לבחור 14 עצמים בעזרת 4 טבעיים, כאשר לא כולם שונים,ללא עם חזרות, איו חשיבות לסדר
n=4
k=14
D(4,13)=(17)!/(14!(3)!)=680

נכפיל את התוצאה ב-6:
6*680=4080



שאלה עם פתרון:
נתונות 6 אותיות a ו-5 ספרות 0.
בכמה אפשרויות ניתן לסדר את התווים הללו כשאסור שתהיינה ספרות באופן רצוף?

תשובה:

מסדרים את 6 האותיות בשורה:
_a_a_a_a_a_a_
יש רק אפשרות אחת כזאת.

נוצרים 7 תאים שונים כפי שאפשר לראות.
צריך לבחור 5 תאים מתוך 7: לא כולם שונים, ללא חזרות וללא חשיבות לסדר.
נשתמש בצירופים בלי חזרות:
k=5
n=7
(p(n,k))/(k!)=(n!)/(k!(n-k)!)
(p(7,5))/(5!)=(7!)/(5!(2)!)=21


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





תורת הגרפים

המשפט היסודי של תורת הגרפים:
נסמן ב-V את קבוצת הצמתים, וב-E את עוצמת הקשתות.
סכום כל הדרגות שווה לפעמיים עוצמת הקשתות.

מסלול על גרף הוא רצף של קשתות סמוכות. קשת לא יכולה לחזור יותר מפעם אחת.

מסלול פשוט הוא מסלול שאינו עובר דרך אותה נקודה יותר מפעם אחת.

אם המסלול מתחיל ונגמר באותה נקודה הריי שזה מעגל.

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

אף מעגל אינו מסלול פשוט

אורך מסלול הוא מספר הקשתות

מרחק בין שתי נקודות: אורך הקשת הקצרה ביותר, גם מסלול ריק נחשב.

המרחק בין שתי נקודות שאין מסלול הוא אינסוף.

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

רכיב קשירות: כל רכיב קשירות הוא בעצם כמו "אי" שאין לו מסלול לנקודות אחרות. אם יש רכיב קשירות אחד הריי שמדובר בגרף קשיר.

בגרף פשוט אין שכנים כפולים (קשתות כפולות), אין לולאות שתורמות פעמיים לדרגה של צומת.
כאשר הגרף הוא פשוט לכל צומת מספר השכנים שלו שווה למספר הדרגה.

טענה יהי G גרף פשוט שבנוי על n צמתים.
נניח שלכל שני צמתים x,y כך ש x שונה מ-y ו x,y אינם שכנים, מתקיים:
d(x)+d(y)>=n-1

הוכח ש-G הוא גרף קשיר.

תשובה:
אנו צריכים להוכיח שבין כל שני צמתים יש מסלול.
(על פי הנתון בין שני שכנים יש מסלול באורך 1 (ישנה קשת אחת).
אנו נבחן את המצב כאשר שני הצמתים לא שווים וגם לא שכנים.

נראה שבין כל שני צמתים x,y יש מסלול:

מקרה ראשון: x=y
יש מסלול באורך 0

מקרה שני: x שונה מ-y, אבל הם שכנים: יש מסלול באורך 1.

מקרה שלישי: x שונה מ-y, אבל הם לא שכנים.
נסמן ב-Nx את קבוצת שכני x
נסמן ב-Ny את קבוצת שכני y
הגרף פשוט ולכן:
d(x)=|Nx|
d(y)=|Ny|
בנוסף ברור ש:
x אינו שייך ל-Nx, משום שמדובר בגרף פשוט
x אינו שייך ל-Ny, כי נתון שהם אינם שכנים.
לכן x אינו שייך ל-Ny איחוד Nx.
באופן אנלוגי:
y אינו שייך ל-Ny איחוד Nx.

לכן:
|Nx איחוד Ny| <= n-2
לפי עיקרון ההכלה וההפרדה:
|Nx איחוד Ny|=|Nx|+|Ny|-|Ny איחוד Nx|

נציב:
d(x)=|Nx|
d(y)=|Ny|

d(x)+d(y)-|Ny איחוד Nx|>=n-1-|Ny חיתוך Nx|
מכאן
n-2>=|Nx חיתוך Ny|=d(x)+d(y)-|Ny חיתוך Nx|>=n-1-|Ny חיתוך Nx|

n-2>=n-1-|Ny חיתוך Nx|
|Ny חיתוך Nx|>=1
לכן ל-x ו-y יש שכן משותף, Z, והמסלול x-z-y הוא מסלול מ-x ל-y.
לכן הגרף קשיר.



שאלה נוספת:
האם קיים גרף בעל 6 צמתים שדרגותיהם: 1,2,3,4,5,6 ?
התשובה היא לא, מפני שסכום הדרגות חייב להיות זוגי, לפי המשפט היסודי: סכום הדרגות הוא פעמיים עוצמת הקשתות.

האם קיים גרף בעל 6 צמתים שדרגותיה: 0,2,2,4,4,4?
התשובה היא כן, סכום הדרגות הוא זוגי, אז תמיד אפשר לבנות גרף עם דרגות כאלה.

כאשר יש צומת מדרגה 0 - הגרף נפסל מלהיות קשיר.


גרפים מיוחדים
הגרף המלא kn, זהו גרף על n צמתים, פשוט, שבין כל שני צמתים שונים מחברת קשת (אחת).

בגרף פשוט אין לולאות, קשתות מקבילות.
באופן כללי ב kn יש n צמתים, ודרגת כל אחת אחת מהם n-1.

kn גרף n-1 רגולי (כל דרגות הצמתים שוות ל n-1)

מספר הקשתות ב-kn הוא n(n-1)/2

גרף דו צדדי - זה גרף שאפשר לחלק את קבוצת הצמתים שלו V לשתי תתי קבוצות לא ריקות A,B כך ש A איחוד B שווה ל-V. בנוסף A חיתוך B שווה לקבוצה הריקה.
וכל קשת בגרף קצה אחד שלה ב-A וקצה שני שלה ב-B.

גרף דו צדדי לא חייב להיות פשוט אבל לא ייתכנו בו לולאות כי אם בנויה על צומת נתון לולאה, אז היא לא משייכת צומת זו גם ל-A וגם ל-B, בסתירה להגדרת גרף דו צדדי.

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


גרף G הוא דו צדדי אם ורק אם איננו מכיל מעגל באורך אי זוגי ויש בו יותר מצומת אחת.

מבין הגרפים השלמים k2 הוא גרף דו צדדי, k1 לא כי יש בו רק צומת אחת.
k3 ומעלה גם לא, כי הגרפים מכילים את k3 ו-k3 הוא מעגל באורך 3.

גרף דו צדדי מלא המסומן kp,q זהו גרף דו צדדי שבנוי על קבוצת צמתים V המחולקת ל-A בגודל P ו-B בגודל q: כך שבין כל צומת ב-A לבין כל צומת ב-B יש קשת אחת.
מספר הצמתים של kp,q הוא p+q.
גרף דו צדדי אינו רגולרי כאשר q שונה מ-p.
יש p צמתים שדרגתם q ו-q צמתים שדרגתם p.
(pq+qp)/2=pq
מספר הדרגות.


מעגלים פשוטים Cn
Cn הוא מעגל פשוט באורך n.
C1 ו-C2 אינם גרפים פשוטים. C3 ומעלה הם גרפים פשוטים.
C3 איזומורה ל-k3.
Cn הוא 2 רגולרי.

Qn קובייה תלת מימדית. הצמתים של Qn הן כל הסדרות הבינאריות באורך n.
בין כל שני צמתים יש קשת אם ורק אם הם נבדלים ביניהם בסיבית אחת בלבד.

באופן כללי ב-Qn יש 2 בחזקת n צמתים. (מספר הסדרות הבינאריות באורך n).
כל צומת היא מדרגה n.
Qn הוא n רגולרי.
לפיכך סכום הדרגות הוא 2 בחזקת n כפול n, ומהספר הקשתות הוא:
n*2^(n-1)

טענה:Qn דו צדדי.
אפשר לשייך את כל הצמתים בעלי סכום סיביות זוגי לקבוצה A.
ואת כל הצמתים בעלי סכום סיביות אי זוגי לקבוצה B, ואז ברור שכל קשת קצה אחד שלה ב-A וקצה שני שלה ב-B.

גרף משלים
נתון גרף G פשוט, על קבוצת צמתים V וקבוצת קשתות E.
הגרף המשלים של G, הוא הגרף שנסמנו ב- G בחזקה c: בנוי מאותה קבוצת צמתים, באופן שכל קשת שקיימת ב-G, אינה קיימת ב-G בחזקת c, ולהיפך.

טענה לפחות אחד מבין הגרפים G ו-G בחזקת c הוא גרף קשיר.

עצים ויערות
גרף שאין בו מעגלים בכלל נקרא יער.
גרף קשיר שאין בו מעגלים נקרא עץ.
ברור שכל יער (ולכן כל עץ) הוא גרף פשוט.
אפשר להגיד שעץ זה יער קשיר.

המשפט היסודי של עצים הוא: אם גרף G הוא עץ בעל n צמתים, אז מספר הקשתות הוא n-1.

שאלה: נתון יער על 14 צמתים, וליער 4 רכיבי קשירות, מהו מספר הקשתות ביער?
פתרון: כל אחד מרכיב הקשירות הוא עץ, יש בו xi צמתים.
x1+x2+x3+x4=14
בכל אחד מרכיבי הקשירות יש xi-1 קשתות (על פי המשפט היסודי של עצים), ולכן מספר הקשתות ביער:
(x1-1)+(x2-1)+(x3-1)+(x4-1)=14
x+x2+x3+x4=10


שאלה: G הוא עץ בעל 60 צמתים.
10 מתוכם בעלי דרגה 3.
כל השאר מדרגות נמוכות יותר.
כמה צמתים מדרגה 1 יש ב-G
פתרון:
נפעיל את המשפט היסודי של תורת הגרפים:
סכום הדרגות שווה פעמיים למספר הקשתות, נסמן ב-x את מספר העלים. (עלים זה צמתים בעלי דרגה אחת)
50-x
יהיה כמובן מספר הצמתים מדרגה 2.
10 הוא מספר הצמתים מדרגה 3.
 נקבל שסכום הדרגות הוא:
x*1+(50-x)*2+10*3=x+100-2x+30=130-x
ועל פי המשפט היסודי סכום הדרגות שווה לפעמיים עוצמת הקשתות: על פי המשפט היסודי של עצים, אם G הוא בעל n צמתים, אז מספר הקשתות הוא n-1:
130-x=2*(60-1)
130-x=118
x=12


שאלה חשובה: כמה עצים שונים אפשר לבנות כל קבוצת הצמתים
{1,2,3,4,5,...n}
תשובה:
n^(n-2)

משפט קיילי: יש פונקציה חח"ע ועל מקבוצת העצים השונים הבנויים על הקבוצה 
{1,2,3,4,5,...n}
לקבוצת הסדרות באורך n-2 הבנויים מ-{1,2,3,4,5,...n}



נתון עץ בן 60 צמתים מתוכם 10 צמתים מדרגה 3, והשאר מדרגה נמוכה יותר.
כמה עלים יש בעץ?
סדרת פרופר היא באורך 58.
מתוכם 20 מקומות נתפסים על ידי 10 הצמתים מדרגה 3.
38 המקומות הנותרים שייכים לפיכך לצמתים מדרגה 2.
ולכן יש 38 צמתים מדרגה 2.
לכן מספר העלים הוא
60-10-38=12
עלים לא מופיעים בסדרה בכלל.


מסלולי אוילר
נתון גרף G עם קבוצת צמתים V וקבוצת קשתות E.
מסלול אוילר פתוח ב-G הוא מסלול פתוח שעובר על כל קשת ב-E.
מעגל אוילר ב-G הוא מעגל (מסלול סגור) שעובר על כל קשת ב-E.

בגרף שאיננו קשיר שבו יש קשתות ביותר מרכיב קשירות אחד, לא יהיה בכלל מסלול אוילר.

בגרף שאיננו קשיר אך רק ברכיב קשירות אחד יש קשתות, השאלה האם יש מסלול אוילר, שקולה לשאלה האם יש מסלול אוילר ברכיב הנ"ל.

משפט בגרף קשיר יש מעגל אוילר אם ורק אם כל הדרגות זוגיות [והגרף איננו נטול קשתות]

בגרף קשיר יש מסלול אוילר פתוח אם כל הדרגות זוגיות פרט ל-2 צמתים בדיוק [ או שהגרף נטול קשתות]

זאת אומרת אם כל הדרגות זוגיות, והגרף קשיר מדובר במעגל אוילר.
אם הדרגות זוגיות פרט ל-2 צמתים בדיוק אז מדובר במסלול אוילר.

יהי G הגרף הבא: הצמתים הם כל תת הקבוצות בגודל 3 של
A={1,2,3,4,5,6,7,8}
בין שני צמתים מחברת קשת אם ורק אם הקבוצות המייצגות את הצמתים זרות.
למשל יש קשת בין {1,2,4} לבין {3,5,6}.
ואין קשת בין {1,2,3} ל-{2,4,6}
מצא כמה צמתים יש בגרף, כמה שקתות יש בגרף. הוכח שהגרף קשיר.
קבע האם יש בגרף מסלול אוילר פשוט, מעגל אוילר או אף אחד מהם.

פתרון:
יש 8 מעל 3 צמתים בגרף [תת קבוצות בגודל 3 של A]. כלומר יש 56 צמתים.
תהא {a,b,c} צומת בגרף.
אנחנו נחשב כמה שכנים יש לה, כאשר כל שכן חייב להיות תת קבוצה בגודל 3 של:
A\{a,b,c}
ומכיוון ש
|A\{a,b,c}|=5
אז מספר השכנים הוא 5 מעל 3, כלומר יש ל-{a,b,c} עשרה שכנים.
לכל צומת יש 10 שכנים.
לכן הגרף הוא 10 רגולרי.
סכום הדרגות הוא 560.
מספר הקשתות הוא 560/2=280
כל הדרגות זוגיות!
נוכיח שהגרף קשיר: יהיו {a,b,c} ו-{d,e,f} שני צמתים שהם לא שווים ולא שכנים [לכן לא זרים], לפיכך
|{a,b,c}|איחוד|{d,e,f}|=5or4
בטוח שיש צומת {l,m,k} שאף אחד מאיבריה לא שייך לאיחוד |{a,b,c}|איחוד|{d,e,f} לכן:

|{l,m,k}|חיתוך|{a,b,c}|=הקבוצה הריקה
|{l,m,k}|חיתוך|{d,e,f}|=הקבוצה הריקה
לכן יש קשת בין |{a,b,c}| ל-|{l,m,k}| ובין |{d,e,f}| ל-|{l,m,k}|
זאת אומרת יש מסלול {a,b,c}-{l,m,k}-{d,e,f}
זאת אומרת בין כל שני צמתים קיים מסלול, לכן הגרף G קשיר, כל דרגותיו זוגיות לפיכך יש בו מעגל אוילר.

מסלולי המילטון
מסלול המילטון פתוח הוא מסלול שעובר דרך כל צומת בגרף
מעגל המילטון הוא מעגל פשוט שעובר דרך כל צומת בגרף

משפט Dirac
אם G גרף בעל n צמתים, ומתקיים n>=3 ולכל צומת בגרף יש דרגה לפחות n/2 אז בגרף G יש מעגל המילטון.

משפט Ore
אם גרף G פשוט בעל n צמתים. n>=3 ולכל שני צמתים x!=y שאינם שכנים, מתקיים 
d(x)+d(y)>=n
אז בגרף G יש מעגל המילטון.



שאלה מבחינה
יהי G גרף פשוט שהצמתים  שלו הם כל תת הקבוצות בנות 3 איברים של
A={1,2,3,4,5,6,7}
ויש קשת בין צומת x לצומת y אם ורק אם
|xחיתוךy|=1
לדוגמה
בין {1,2,3} ל-{3,4,5} יש קשת
בין {2,3,4} ל-{1,2,3} אין קשת
בין {4,5,6} ל- {1,2,3} אין קשת

הוכח שב-G יש מעגל המילטון.

פתרון:
מספר הצמתים ב-G (כל תת הקבוצות בגודל 3 של A):
הוא 7 מעל 3, זאת אמורת מספר הצמתים ב-G הוא 35.
G פשוט מעצם הגדרתו, נבחר צומת כלשהי {a,b,c}.
השכן של הצומת הנבחרת חייב להכיל בדיוק מספר אחד מבין a,b,c ויש 3 אפשרויות לכך, ובדיוק 2 מספרים מהמשלים:
|A\{a,b,c}|=4
מספר האפשרויות למצוא שכן לצומת {a,b,c}, כאשר אנחנו רוצים לבחור 2 איברים מתוך המשלים של הצומת, כי איבר אחד אמור להישאר הוא 3 כפול 4 מעל 2: 18.
זאת אומרת סה"כ 18 אפשרויות לשכנים עבור {a,b,c}, לכן דרגת d({a,b,c})=18, זה נכון לכל צומת בגרף.

זהו גרף  18 רגולרי. ולכן לכל צומת מתקיים תנאי משפט דיראק.
18>35/2
לפיכך ב-G יש מעגל המילטון [וגם מסלול המילטון].
יש בו גם מעגל אוילר כי הוא קשיר (כהמילטון), וכל דרגותיו זוגיות.
אין בו מסלול אוילר פתוח!

זיווג בגרף זהו אוסף של קשתות (לא לולאות) בגרף שלאף שניים מהם אין קצה משותף.

מספר הקשתות בזיווג מושלם n/2
שאין זיווג מושלם יש זיווג מקסימלי שיאנו מושלם.

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

שאלה
תהי A קבוצת כל הקבוצות בנות 3 איברים שחלקיות ל-
B={1,2,3,4}
כלומר
A={{1,2,3},{1,2,4},{1,3,4},{2,3,4}}
נסמן ב-G את הגרף הדו צדדי המוגדר כך:
קבוצת הצמתים AאיחודB, כאשר A ו-B הם הצדדים.
ולכן לכל צומת ב-A יש קשת בינה לבין צומת ב-B אם ורק אם הצומת ב-B היא האיבר המקסימלי או המינימלי של הצומת ב-A.
בחר בתשובה הנכונה:
1. קיים ב-G זיווג המזווג את כל צומתי A שבו {1,2,3} מזווג ל-1
2. קיים ב-G זיווג המזווג את כל צומתי A שבו {1,2,3} מזווג ל-3.
3. יש רק דרך אחת לזווג את כל צומתי A.

התשובה הנכונה היא 2.


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

גרף דו צדדי מלא שאחד הצדדים הוא בגודל 2 הוא תמיד מישורי (למשל k2,9)

בכל גרף מישורי מספר הפאות קבוע

משפט אוילר
בכל גרף מישורי קשיר בעל n צמתים ו-m קשתות, מספר הפאות f נקבע באופן יחיד, על פי הנוסחה
f=m-n+2
k3,3 איננו מישורי
k5 איננו מישורי

m<=3n-6
גרף כלשהו צריך לקיים על מנת שיהיה מישורי

גרף דו צדדי:
m<=2n-4


כל עידון של k5 אינו יכול להיות מישורי, זאת אומרת ש-k5 הוא תת גרף שלו (מוחקים קשתות בלבד או צומת עם קשותיו).

בגרף דו צדדי מלא ומישורי על 8 צמתים יש לכל היותר:
1. 4 פאות
2.6 פאות
3. 8 פאות

פתרון: יש רק שני גרפים שעונים על הדרישה: דו צדדי מלא על 8 צמתים.