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

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

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

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

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

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

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

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

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

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

רמת קושי:

יהי

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 · סמסטר ג

★★★★★

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

יהי

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 · סמסטר ג

★★★★★

גרפיםגרף אוילרי

נתון:

T

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

G

גרף פשוט על

V (T)

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

T

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

G

הן

d - 1

; ב-

G

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

א. הוכיחו כי

G

קשיר.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד א' 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 · סמסטר ג

★★★★★

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

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

n \geq 2

שלם, ויהי

T

עץ על

n

צמתים.

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

\overline{T}

קשיר, אז לפחות שניים מהצמתים של

T

אינם עלים ב-

T

.

(9 נק') ב. הוכיחו, שאם לפחות שניים מהצמתים של

T

אינם עלים ב-

T

, אז

\overline{T}

קשיר.
(הדרכה: כדאי להוכיח תחילה, שכל רכיב קשירות של

\overline{T}

הוא בגודל 2 לפחות.)

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

\overline{T}

אוילרי, אז מתקיים התנאי הבא: לכל

v \in V (T)

, הסכום

de g_{T} (v) + n

הוא מספר אי-זוגי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

האוניברסיטה הפתוחהמועד 59 · 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 · סמסטר א

★★★★★

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

יהי

n

מספר שלם וחיובי. נתון ש-

T

עץ על

n

צמתים. כמו כן, נתון ש-

G

גרף המתקבל מ-

T

על-ידי הוספת צומת חדש יחיד

v

וחיבורו בקשת לכל אחד מהצמתים של

T

.
(14 נק') א. לכל אחת מהטענות הבאות, קבעו האם היא נובעת מהנתון. נמקו היטב.
1) אם

G

אוילרי, אז

n

זוגי.
2) אם

n

זוגי, אז

G

אוילרי.
(13 נק') ב. הוכיחו, כי אם

G

המילטוני אז מספר העלים של

T

הוא 2.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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