איך לתרגל שאלות גרף המילטוני במתמטיקה בדידה?

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

כמה שאלות גרף המילטוני יש במתמטיקה בדידה?

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

מה חשוב לדעת על גרף המילטוני לקראת מבחן במתמטיקה בדידה?

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

מתמטיקה בדידה - גרף המילטוני

לוגיקה, תורת הקבוצות, קומבינטוריקה וגרפים

סטטיסטיקות מבחנים

תתי-נושאים של גרפים

רמת קושי:

יהי

G

גרף פשוט על עשרה צמתים, שמספר הקשתות שלו הוא 38.
(6 נק') א. יהיו

u, v

שני צמתים שונים של

G

. האם קיימות 29 קשתות של

G

, שאף אחת מהן אינה סמוכה (ב-

G

) ל-

u

ואף אחת מהן אינה סמוכה ל-

v

? הוכיחו את תשובתכם.
(7 נק') ב. הוכיחו, כי

G

המילטוני.
(7 נק') ג. הוכיחו, כי

G

מכיל מעגל באורך 9.
(תוכלו לפעול כך: להראות כי יש ב-

G

מעגל פשוט

C

באורך 10, ואז להראות, כי קיימת קשת של

G

, שבעזרתה ניתן "לדלג על צומת של

C

" ולקבל מ-

C

מעגל באורך 9. הקפידו לנסח את טיעוניכם במדויק.)
(7 נק') ד. הוכיחו, כי המרחק ב-

G

בין כל שני צמתים שונים של

G

הוא לכל היותר 2.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א1 · 2026 · סמסטר א

★★★★★

גרפיםגרף המילטוניהוכחה

יהי

G

גרף פשוט על עשרה צמתים. נתון של-

\overline{G}

(המשלים של

G

) יש בדיוק שלושה רכיבי קשירות, שלפחות אחד מהם הוא בגודל 4. כמו כן, נתון שתת-הגרף של

\overline{G}

המושרה על-ידי כל אחד מרכיבי הקשירות שלו הוא גרף מלא, וכן שמספר הקשתות של

G

הוא 33.
(9 נק') א. מהם הגדלים של שלושת רכיבי הקשירות של

\overline{G}

? נמקו היטב. (התשובה הסופית צריכה להיות שלשת מספרים). (הדרכה: כדאי למצוא תחילה את מספר הקשתות של

\overline{G}

.)
(9 נק') ב. 1) מצאו את דרגות כל הצמתים ב-

\overline{G}

. נמקו היטב. (התשובה הסופית צריכה להיות סדרת מספרים באורך 10.)
2) מצאו את דרגות הצמתים ב-

G

. נמקו היטב.
(9 נק') ג. האם

G

אוילרי? האם הוא המילטוני? הוכיחו את תשובותיכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א2 · 2026 · סמסטר א

★★★★★

גרפיםקש"בגרף אוילריגרף המילטוניגרף משלים

נתון:

T

עץ מתייג, שקבוצת התגים שלו היא

{1, 2, 3, 4, 5, 6, 7, 8}

. עוד נתון, שסדרת פרופר של

T

היא

⟨ 1, 8, 8, 1, 3, 8 ⟩

.

בחרו את התשובה הנכונה:

[1] יש זוג צמתים שכנים ב-

T

, שכל אחד מהם הוא שכן (ב-

T

) של שני עלים לפחות.

[2] יש גרף מילטוני, שמתקבל מ-

T

על-ידי הוספת ארבע קשתות.

[3] יש גרף אוילרי, שמתקבל מ-

T

על-ידי הוספת שתי קשתות.

[4] יש זוג צמתים שכנים ב-

T

, שאף אחד מהם אינו שכן של עלה.

[5] אף אחת מהטענות [1]–[4] אינה נכונה.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א' 2025 · 2025 · סמסטר ג

★★★★★

עציםסדרת פרופרגרף אוילריגרף המילטוני

השאלה מיועדת רק למי שלמדו את הקורס בסמסטר 2025א, בסמסטר 2025ב, בסמסטר 2025ג, או לפני שנת הלימודים 2024!

יהי

G

גרף פשוט, קשיר ולא מישורי על 7 צמתים, שמספר הקשתות שלו הוא 11 ודרגת כל צומת בו היא לפחות 3.

(9 נק') א. הוכיחו כי

G

אינו מכיל, כתת-גרף, העדנה של

K_{5}

.

(9 נק') ב. הוכיחו כי ל-

G

יש תת-גרף פורש, המהווה העדנה של

K_{3, 3}

.

(9 נק') ג. הוכיחו כי

G

המילטוני. תוכלו להיעזר בטענה הבאה מבלי להוכיח אותה: לכל קשת

e

של

K_{3, 3}

, יש מעגל המילטון

C

ב-

K_{3, 3}

כך ש-

e

מופיעה ב-

C

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 91 · 2025 · סמסטר ג

★★★★★

גרפיםגרף מישוריגרף המילטוניהוכחה

יהי

n \geq 4

שלם, יהיו

v_{1}, \dots, v_{n - 1}

העלים של

K_{1, n - 1}

, ויהי

G_{n}

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

⟨ v_{1}, v_{2}, v_{3}, \dots, v_{n - 1}, v_{1} ⟩

, ובין כל זוג צמתים

v_{i}, v_{2 i}

שעבורם

i, 2 i \in {2, 3, \dots, n - 1}

.

ג. האם

G_{n}

המילטוני? הוכיחו את תשובתכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א' 2025 · 2025 · סמסטר ג

★★★★★

גרפיםגרף המילטוני

השאלה מיועדת רק למי שלמדו את הקורס בשנת הלימודים 2024!

לכל גרף

G

נתאים גרף

L (G)

, שיקרא גרף הקשתות של

G

, ושמקיים את התנאים הבאים:

L (G)

גרף פשוט, קבוצת צמתיו היא

E (G)

, ולכל

u, v \in E (G)

מתקיים התנאי הבא:

u, v

הם צמתים שכנים ב-

L (G)

אם"ם הם קשתות שונות של

G

, שיש להן צומת משותף ב-

G

(כלומר: יש צומת ששתיהן סמוכות אליו ב-

G

).

(9 נק') א. הוכיחו: אם

G

אוילרי, אז

L (G)

המילטוני.

(9 נק') ב. הפריכו את הטענה הבאה בעזרת דוגמה נגדית: לכל גרף

G

, אם

L (G)

המילטוני, אז

G

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

(9 נק') ג. הוכיחו:
אם

G

גרף פשוט ויש צומת שדרגתו ב-

G

היא לפחות 5, אז

L (G)

אינו מישורי.
תוכלו להסתמך על הטענה הבאה מבלי להוכיח אותה: כל תת-גרף של גרף מישורי הוא גרף מישורי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 91 · 2025 · סמסטר ג

★★★★★

גרפיםגרף אוילריגרף המילטוניגרף מישוריהוכחה

נתון:

T

עץ על ארבעה צמתים לפחות;

G

גרף פשוט על

V (T)

, שמספר קשתותיו גדול ב-2 מזה של

T

; דרגות כל הצמתים ב-

G

הן

d - 1

; ב-

G

יש מסלול אוילר שאינו מעגל.

ג. הוכיחו, כי אם

G

המילטוני אז יש בו שני צמתים שכנים שדרגותיהם אי-זוגיות.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א' 2025 · 2025 · סמסטר ג

★★★★★

גרפיםגרף המילטוני

השאלה מיועדת רק למי שלמדו את הקורס בסמסטר 2025א, בסמסטר 2025ב, או לפני שנת הלימודים 2024!
נתון, ש-

G

גרף פשוט ולא מישורי על 7 צמתים. כמו כן, נתון ש-

∣ E (G) ∣ = 11

, וש-

de g_{G} (v) \geq 3

לכל

v \in V (G)

.

(9 נק') א. הוכיחו ש-

G

מכיל, כתת-גרף, העדנה של

K_{3, 3}

.

(9 נק') ב. הוכיחו ש-

G

המילטוני.
תוכלו להיעזר בטענה הבאה מבלי להוכיח אותה: כל גרף, המתקבל מ-

K_{3, 3}

על-ידי פעולה יחידה של עידון קשת, הוא המילטוני.
(הדרכה: הוכיחו תחילה, כי

G

מכיל, כתת-גרף, העדנה של

K_{3, 3}

שכל צמתי

G

הם צמתים שלה.)

(9 נק') ג. האם

G

אוילרי? הוכיחו את תשובתכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 59 · 2025 · סמסטר ב

★★★★★

גרפיםגרף מישוריגרף המילטוניגרף אוילריהוכחה

השאלה מיועדת רק למי שלמדו את הקורס בשנת הלימודים 2024 בלבד.
שאלה: נתון, כי

G

גרף פשוט על

n

צמתים, ובו שני מעגלי המילטון

C_{1}, C_{2}

שאין להם אף קשת משותפת. עוד נתון, כי כל אחת מהקשתות של

G

מופיעה באחד המעגלים

C_{1}, C_{2}

.
א. (9 נק') האם

G

אוילרי? הוכיחו את תשובתכם.
ב. (9 נק') הוכיחו, כי אם

G

מישורי אזי ל-

\overline{G}

(המשלים של

G

) אין אף צומת מבודד.
ג. (9 נק') הוכיחו, שאם

n \geq 7

ו-

G

מישורי, אז

\overline{G}

קשיר.
תוכלו להסתמך על הטענה הבאה מבלי להוכיח אותה: כל-תת גרף של גרף מישורי הוא גרף מישורי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 84 · 2025 · סמסטר ב

★★★★★

גרפיםגרף אוילריגרף המילטוניגרף מישוריהוכחהקש"ב

בחרו את התשובה הנכונה בכל סעיף. כתבו את התשובות במחברת הבחינה.
בשאלה זו בלבד אין צורך בהוכחה.

(6 נק') א. נתון ש-

A \subseteq N

. כמו כן, נתון שהפסוק הבא הוא אמת, כאשר תחום הדיון (ההקשר) הוא

{A, 0, 1, 2, 3, \dots}

\neg\forall x ((x \in A) \to (x + 1 \in A))

[1] מהנתונים נובע כי

A = N

.
[2] מהנתונים נובע כי

\emptyset \subset A \subset N

.
[3] מהנתונים לא נובע כי

\emptyset \subset A \subset N

, אבל כן נובע כי

\emptyset \subseteq A \subseteq N

.
[4] מהנתונים נובע כי

A = \emptyset

.

(7 נק') ב. קטע פתוח שאורכו סופי הוא קבוצה מהצורה

{x \in R ∣ a < x < b}

, כאשר

a, b \in R

.
נתון ש-

A

קבוצת כל הקטעים הפתוחים שאורכם סופי. אזי:
[1]

∣ A ∣ < ℵ_{0}

.
[2]

∣ A ∣ = ℵ_{0}

.
[3]

∣ A ∣ = ℵ

.
[4]

∣ A ∣ > ℵ

.

(6 נק') ג. נתון ש-

G

גרף המילטוני וגם אוילרי. (לא נתון ש-

G

גרף פשוט.)
[1] מהנתון נובע ש-

G

הוא מעגל פשוט.
[2] מהנתון לא נובע ש-

G

הוא מעגל פשוט, אבל מהנתון כן נובע ש-

G

הוא מעגל.
[3] מהנתון נובע, כי ב-

G

יש מעגל המילטון שהוא גם מעגל אוילר.
[4] אף אחת מהטענות [1]–[3] אינה נכונה.
הערה: משמעות הטענה "

G

הוא מעגל" היא זו: יש ב-

G

מעגל, שכל הקשתות והצמתים של

G

מופיעים בו.
משמעות הטענה "

G

הוא מעגל פשוט" היא זו: יש ב-

G

מעגל פשוט, שכל הקשתות והצמתים של

G

מופיעים בו.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 83 · 2025 · סמסטר א

★★★★★

לוגיקהפסוקיםקבוצותעוצמותמכפלה קרטזיתגרפיםגרף אוילריגרף המילטוני

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

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