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

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

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

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

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

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

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

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

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

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

רמת קושי:

השאלה מיועדת רק למי שלמדו את הקורס בסמסטר 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 · סמסטר ג

★★★★★

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

השאלה מיועדת רק למי שלמדו את הקורס בשנת הלימודים 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 · סמסטר ג

★★★★★

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

יהי

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}

.

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

n \geq 7

, אז

G_{n}

אינו מישורי.

*(הדרכה: נסו להראות ש-

G_{n}

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

K_{5}

, והיעזרו במשפט מתאים.)*

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G

הוא גרף לא-מישורי מינימלי אם הוא קשיר, לא מישורי, ולכל

e \in E (G)

, הגרף המתקבל מ-

G

על-ידי מחיקת

e

הוא מישורי.
יהי

G

גרף לא-מישורי מינימלי, ויהי

H

גרף המתקבל מ-

G

על-ידי מחיקת קשת אחת.
א. (14 נק') הוכיחו, שיש קבוצה לא ריקה

X \subseteq V (G)

, המקיימת את התנאים הבאים: (i) יש מעגל ב-

G

שכל איברי

X

מופיעים בו; (ii) כל

v \in V (G) ∖ X

הוא בעל דרגה זוגית ב-

G

. היעזרו במשפט קורטובסקי.
תוכלו להשתמש בטענות הבאות מבלי להוכיח אותן:
(i)

K_{5}

ו-

K_{3, 3}

הם גרפים המילטוניים.
(ii) אם

C

מעגל בגרף

J

ו-

J^{'}

העדנה של

J

, אז ב-

J^{'}

יש מעגל שבו מופיעים כל הצמתים המופיעים ב-

C

.
ב. (13 נק') הוכיחו, כי

H

קשיר. (ניתן להיעזר כאן בסעיף א'.)

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

גרפיםגרף מישוריהוכחהקש"ב

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

(9 נק') א. נתבונן בתנאי הבא על גרף

H

∣ E (H) ∣ \geq ∣ V (H) ∣ + 3 (*)

הוכיחו, כי אם גרף

H

הוא העדנה של

K_{3, 3}

או של

K_{5}

, אזי הוא מקיים את

(*)

.

(9 נק') ב. יהי

G

גרף לא מישורי, המתקבל מעץ

T

על-ידי הוספת

k

קשתות בדיוק.
הוכיחו כי

k \geq 4

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

H

מתקיים

∣ E (H) ∣ \leq ∣ V (H) ∣ - 1

.

(9 נק') ג. יהי

n \in N

. הוכיחו כי כל גרף קשיר

G

על

n

צמתים, המקיים

∣ E (G) ∣ \leq n + 2

, הוא מישורי.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

G

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

H

גרף מישורי ופשוט, שמתקבל מ-

G

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

H

הוא 5, ודרגת כל צומת בו גדולה ב-1 מדרגת אותו צומת ב-

G

.
(14 נק') א. מצאו את מספר הקשתות ואת מספר הצמתים של

H

.
(13 נק') ב. מצאו את

χ (H)

. הוכיחו את תשובתכם.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

גרפיםגרף מישוריקש"במספר כרומטי

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

G

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

H

גרף מישורי ופשוט, שמתקבל מ-

G

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

H

הוא 5, ודרגת כל צומת בו גדולה ב-1 מדרגת אותו צומת ב-

G

.
(14 נק') א. מצאו את מספר הקשתות ואת מספר הצמתים של

H

.
(6 נק') ב. הוכיחו כי

H

המילטוני.
(7 נק') ג. האם

\overline{H}

המילטוני? נמקו היטב.

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

נתון ש-

G = (V, E)

הוא גרף מישורי, קשיר ופשוט על

7

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

G

בעל 10 פאות.

(14 נק') א.
1. מיצאו את מספר הקשתות של

G

.
2. הראו שאם שני צמתים שונים של

G

שאינם שכנים ב-

G

, מקבלים גרף לא מישורי.

(13 נק') ב. הוכיחו שאם ב-

G

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

העתק שאלה

שתף שאלה

סמן כחשוב

סמן כבוצע

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

★★★★★

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

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

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