הוספת קשת ויצירת מעגל
עריכה
אנא הוכח שהוספת קשת לעץ בהכרח תיצור מעגל.
נניח שנוסיף לגרף את הקשת
(
u
,
v
)
{\displaystyle \displaystyle (u,v)}
העץ לפני הקשת נזכור שעץ הוא קשיר עפ"י ההגדרה, ולכן לפני הוספת הקשת , היה מסלול
P
{\displaystyle \displaystyle P}
u
{\displaystyle \displaystyle u}
v
{\displaystyle \displaystyle v}
העץ לפני הקשת - מסלול מודגש לכן, לאחר הוספת הקשת
(
u
,
v
)
,
{\displaystyle \displaystyle (u,v),}
u
{\displaystyle \displaystyle u}
P
{\displaystyle \displaystyle P}
(
u
,
v
)
{\displaystyle \displaystyle (u,v)}
העץ לפני הקשת - המעגל הגדרות שקולות לעץ
עריכה
נתון גרף לא-מכוון
G
=
(
V
,
E
)
{\displaystyle \displaystyle G=(V,E)}
G
{\displaystyle \displaystyle G}
G
{\displaystyle \displaystyle G}
|
E
|
=
|
V
|
−
1
{\displaystyle \displaystyle |E|=|V|-1}
אנא הוכח שכל שתיים משלוש התכונות בהכרח גוררת את התכונה הנותרת.
רמז לגרירה
1
∧
3
→
2
{\displaystyle \displaystyle 1\wedge 3\rightarrow 2}
נניח בשלילה ש1 ו3 מתקיימים, אך יש מעגל.
הסבר מדוע בפשטות לא ייתכן שהמעגל כולל את כל הצמתים.
נניח שהמעגל אינו כולל את כל הצמתים. חשוב מה יקרה כשנוסיף לגרף, מעבר למעגל, עוד צמתים וקשתות.
משפט:
אם
G
=
(
V
,
E
)
{\displaystyle \displaystyle G=(V,E)}
|
E
|
=
|
V
|
−
1
{\displaystyle \displaystyle |E|=|V|-1}
הוכחה: הוכחנו זאת כבר בהרצאה .
משפט:
אם
G
=
(
V
,
E
)
{\displaystyle \displaystyle G=(V,E)}
|
E
|
=
|
V
|
−
1
{\displaystyle \displaystyle |E|=|V|-1}
G
{\displaystyle \displaystyle G}
הוכחה: כל גרף חסר מעגלים הוא יער; בפרט, נניח שמדובר ביער בעל
i
{\displaystyle \displaystyle i}
i
=
1
{\displaystyle \displaystyle i=1}
i
>
1
{\displaystyle \displaystyle i>1}
j
{\displaystyle \displaystyle j}
|
V
j
|
{\displaystyle \displaystyle |V_{j}|}
|
V
j
|
−
1
{\displaystyle \displaystyle |V_{j}|-1}
∑
j
=
1
i
|
V
j
|
{\displaystyle \displaystyle \sum _{j=1}^{i}|V_{j}|}
∑
j
=
1
i
[
|
V
j
|
−
1
]
=
∑
j
=
1
i
|
V
j
|
−
i
<
|
V
|
−
1
{\displaystyle \displaystyle \sum _{j=1}^{i}[|V_{j}|-1]=\sum _{j=1}^{i}|V_{j}|-i<|V|-1}
משפט:
אם
G
=
(
V
,
E
)
{\displaystyle \displaystyle G=(V,E)}
|
E
|
=
|
V
|
−
1
{\displaystyle \displaystyle |E|=|V|-1}
G
{\displaystyle \displaystyle G}
הוכחה: נניח שבגרף יש מעגל בעל
n
′
≤
n
{\displaystyle \displaystyle n'\leq n}
n
′
{\displaystyle \displaystyle n'}
n
′
=
n
{\displaystyle \displaystyle n'=n}
|
E
|
=
|
V
|
−
1
{\displaystyle \displaystyle |E|=|V|-1}
n
′
<
n
{\displaystyle \displaystyle n'<n}
G
1
′
{\displaystyle \displaystyle G'_{1}}
מספירה פשוטה, קל לראות שקיים צומת כלשהו ב
G
{\displaystyle \displaystyle G}
G
1
′
{\displaystyle \displaystyle G'_{1}}
G
{\displaystyle \displaystyle G}
G
1
′
{\displaystyle \displaystyle G'_{1}}
G
2
′
{\displaystyle \displaystyle G'_{2}}
G
2
′
{\displaystyle \displaystyle G'_{2}}
n
′
+
1
{\displaystyle \displaystyle n'+1}
n
′
+
1
{\displaystyle \displaystyle n'+1}
מספירה פשוטה, קל לראות שקיים צומת כלשהו ב
G
{\displaystyle \displaystyle G}
G
2
′
{\displaystyle \displaystyle G'_{2}}
G
{\displaystyle \displaystyle G}
G
2
′
{\displaystyle \displaystyle G'_{2}}
G
3
′
{\displaystyle \displaystyle G'_{3}}
G
3
′
{\displaystyle \displaystyle G'_{3}}
n
′
+
2
{\displaystyle \displaystyle n'+2}
n
′
+
2
{\displaystyle \displaystyle n'+2}
...
מספירה פשוטה, קל לראות שקיים צומת כלשהו ב
G
{\displaystyle \displaystyle G}
G
n
−
n
′
′
{\displaystyle \displaystyle G'_{n-n'}}
G
{\displaystyle \displaystyle G}
G
n
−
n
′
′
{\displaystyle \displaystyle G'_{n-n'}}
G
n
−
n
′
+
1
′
{\displaystyle \displaystyle G'_{n-n'+1}}
G
n
−
n
′
+
1
′
{\displaystyle \displaystyle G'_{n-n'+1}}
n
{\displaystyle \displaystyle n}
n
{\displaystyle \displaystyle n}
|
E
|
=
|
V
|
−
1
{\displaystyle \displaystyle |E|=|V|-1}
![{\displaystyle \displaystyle \sum _{j=1}^{i}[|V_{j}|-1]=\sum _{j=1}^{i}|V_{j}|-i<|V|-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b15ffc16261fa81aceb8bb1659942de8a24f81dd)
