תקציר תורת הגרפים, סמסטר א תשע״ג - היסטוריית גרסאות

אור שחף: /* משפטים */

2013-02-13T15:37:02Z

משפטים

→ הגרסה הקודמת		גרסה מ־15:37, 13 בפברואר 2013
שורה 157:		שורה 157:
	* גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.		* גרף הוא עץ אם״ם הוא מקסימלי ללא מעגלים, כלומר הוא עץ וכל הוספת צלע יוצרת מעגל.
	* לכל גרף קשיר וסופי קיים עץ פורש.		* לכל גרף קשיר וסופי קיים עץ פורש.
	* ~~מספר העצים הפורשים של גרף של~~ <math>~~K_n~~</math> ~~הוא~~ <math>n~~^{n-2}~~</math>.		* '''משפט קיילי:''' יש <math>n^{n-2}</math> עצים מסומנים מסדר <math>n</math>.
	* '''משפט מטריצה–עץ/משפט עצים פורשים:''' כידוע, מינור <math>A[i,j]</math> של מטריצה <math>A</math> הוא המטריצה המתקבלת מהשמטת השורה ה־<math>i</math> והעמודה ה־<math>j</math>. נסמן <math>\hat A</math> כמינור המוחק את השורה והעמודה האחרונות. עתה יהי <math>G</math> גרף לא מכוון וסופי מסדר הגדול מ־1. מספר העצים הפורשים שלו שווה ל־<math>\det\!\left(\hat L_G\right)</math>.		* '''משפט מטריצה–עץ/משפט עצים פורשים:''' כידוע, מינור <math>A[i,j]</math> של מטריצה <math>A</math> הוא המטריצה המתקבלת מהשמטת השורה ה־<math>i</math> והעמודה ה־<math>j</math>. נסמן <math>\hat A</math> כמינור המוחק את השורה והעמודה האחרונות. עתה יהי <math>G</math> גרף לא מכוון וסופי מסדר הגדול מ־1. מספר העצים הפורשים שלו שווה ל־<math>\det\!\left(\hat L_G\right)</math>.
	* '''בעיית הסוכן הנוסע:''' נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.		* '''בעיית הסוכן הנוסע:''' נתו גרף קשיר וסופי ורוצים למצוא את ההילוך הקצר ביותר העובר דרך כל קודקודי הגרף. הפתרון הכי יעיל לא ידוע, אבל יש פתרון הנותן הילוך שאורכו לכל היותר פי 2 מהפתרון המינימלי: מוצאים עץ פורש לגרף ומבצעים עליו חיפוש DFS.
שורה 174:		שורה 174:
	** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).		** וקטור דרגות (וקטור דרגות של גרף הוא וקטור שרכיביו הם דרגות הקודקודים מסודרות בסדר יורד חלש).
	** קוטר: <math>\operatorname{diameter}(G)=\operatorname{diameter}(H)</math>.		** קוטר: <math>\operatorname{diameter}(G)=\operatorname{diameter}(H)</math>.
	* '''משפט קיילי:''' יש <math>n^{n-2}</math> עצים מסומנים מסדר <math>n</math>.
	* <math>G\cong H</math> אם״ם <math>\overline G\cong\overline H</math>.		* <math>G\cong H</math> אם״ם <math>\overline G\cong\overline H</math>.
	* <math>L(P_n)\cong P_{n-1},L(C_n)\cong C_n</math>.		* <math>L(P_n)\cong P_{n-1},L(C_n)\cong C_n</math>.

אור שחף: /* אי־תלות */

2013-02-13T15:20:54Z

אי־תלות

→ הגרסה הקודמת		גרסה מ־15:20, 13 בפברואר 2013
שורה 130:		שורה 130:
	=== אי־תלות ===		=== אי־תלות ===
	* '''קבוצה בלתי־תלויה של צלעות''' בגרף <math>G</math> היא תת־קבוצה של <math>E(G)</math> שבה אין שתי צלעות בעלות קודקוד משותף.		* '''קבוצה בלתי־תלויה של צלעות''' בגרף <math>G</math> היא תת־קבוצה של <math>E(G)</math> שבה אין שתי צלעות בעלות קודקוד משותף.
	* '''קבוצה ~~בלתי תלויה~~ של קודקודים''' בגרף <math>G</math> היא תת־קבוצה של <math>V(G)</math> שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.		* '''קבוצה בלתי־תלויה של קודקודים''' בגרף <math>G</math> היא תת־קבוצה של <math>V(G)</math> שמשרה גרף ריק, כלומר שבה אין שני קודקודים שכנים.
	* <math>\alpha(G)</math> הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־<math>G</math>.		* <math>\alpha(G)</math> הוא הגודל המקסימלי של קבוצה בלתי־תלויה של קודקודים ב־<math>G</math>.

אור שחף: /* מכפלה קרטזית של גרפים */

2013-02-13T15:18:46Z

מכפלה קרטזית של גרפים

→ הגרסה הקודמת		גרסה מ־15:18, 13 בפברואר 2013
שורה 92:		שורה 92:

	==== מכפלה קרטזית של גרפים ====		==== מכפלה קרטזית של גרפים ====
	* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> (כשהקודקודים הם זוגות סדורים) וצלעותיו <math>~~\Big\{~~\Big((u_1,v),(u_2,v)\Big):\ \~~forall~~ \~~{F_1~~,~~F_2~~\}=\{G,H\~~}:\ v~~\in V(~~F_1~~)\ \and\ (~~u_1~~,~~u_2~~)\in E(~~F_2~~)~~\Big\}~~</math> ~~(כשהצלעות זוגות לא סדורים של קודקודים)~~.		* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> (כשהקודקודים הם זוגות סדורים) וצלעותיו <math>\Big((v,u_1),(v,u_2)\Big)</math> כאשר <math>v\in V(G)\ \and\ (u_1,u_2)\in E(H)</math> או <math>\Big((v_1,u),(v_2,u)\Big)</math> כאשר <math>u\in V(H)\ \and\ (v_1,v_2)\in E(G)</math>.
	* '''קובייה ''n''־מימדית''' היא <math>K_2^{\times n}:=\prod_{i=1}^n K_2</math>.		* '''קובייה ''n''־מימדית''' היא <math>K_2^{\times n}:=\prod_{i=1}^n K_2</math>.

אור שחף: /* מכפלה קרטזית של גרפים */

2013-02-13T15:06:31Z

מכפלה קרטזית של גרפים

→ הגרסה הקודמת		גרסה מ־15:06, 13 בפברואר 2013
שורה 92:		שורה 92:

	==== מכפלה קרטזית של גרפים ====		==== מכפלה קרטזית של גרפים ====
	* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> וצלעותיו <math>\Big\{\Big((u_1,v),(u_2,v)\Big):\ \forall \{F_1,F_2\}=\{G,H\}:\ v\in V(F_1)\ \and\ (u_1,u_2)\in E(F_2)\Big\}</math>.		* '''המכפלה הקרטזית''' של הגרפים <math>G,H</math> היא גרף המסומן כ־<math>G\times H</math>. קודקודיו הם <math>V(G)\times V(H)</math> (כשהקודקודים הם זוגות סדורים) וצלעותיו <math>\Big\{\Big((u_1,v),(u_2,v)\Big):\ \forall \{F_1,F_2\}=\{G,H\}:\ v\in V(F_1)\ \and\ (u_1,u_2)\in E(F_2)\Big\}</math> (כשהצלעות זוגות לא סדורים של קודקודים).
	* '''קובייה ''n''־מימדית''' היא <math>K_2^{\times n}:=\prod_{i=1}^n K_2</math>.		* '''קובייה ''n''־מימדית''' היא <math>K_2^{\times n}:=\prod_{i=1}^n K_2</math>.

אור שחף: /* משפטים */

2013-02-13T12:11:00Z

משפטים

→ הגרסה הקודמת		גרסה מ־12:11, 13 בפברואר 2013
שורה 193:		שורה 193:
	* גרף הוא 2־צביע אם״ם הוא דו־צדדי.		* גרף הוא 2־צביע אם״ם הוא דו־צדדי.
	* '''בעיית 4 הצבעים:''' לכל גרף מישורי סופי פשוט <math>G</math> הוא 4־צביע.		* '''בעיית 4 הצבעים:''' לכל גרף מישורי סופי פשוט <math>G</math> הוא 4־צביע.
	* <math>f_{N_n}(x)=x^n\ \and\ f_{K_n}(x)=(x)_n=\~~begin~~{~~cases~~}~~\frac~~{x!}{(x-n)~~!},&x\ge n\\0,&\text{else}\end{cases}~~\ \and\ f_{P_n}(x)=x(x-1)^{n-1}</math>.		* <math>f_{N_n}(x)=x^n\ \and\ f_{K_n}(x)=(x)_n=\prod_{i=0}^{n-1}(x-i)\ \and\ f_{P_n}(x)=x(x-1)^{n-1}</math>.
	* <math>\forall x\in\mathbb N\ \and\ e\in E(G):\ f_G(x)=f_{G\setminus e}(x)-f_{G/e}(x)</math>.		* <math>\forall x\in\mathbb N\ \and\ e\in E(G):\ f_G(x)=f_{G\setminus e}(x)-f_{G/e}(x)</math>.
	* <math>f_G</math> פולינום מתוקן ודרגתו <math>\|V(G)\|</math>.		* <math>f_G</math> פולינום מתוקן ודרגתו <math>\|V(G)\|</math>.
שורה 214:		שורה 214:
	* מספר ההילוכים מ־<math>v_i</math> ל־<math>v_j</math> מאורך <math>t</math> הוא <math>(A_G^t)_{i,j}</math>.		* מספר ההילוכים מ־<math>v_i</math> ל־<math>v_j</math> מאורך <math>t</math> הוא <math>(A_G^t)_{i,j}</math>.
	* מספר ההילוכים הסגורים מאורך <math>t</math> ב־<math>G</math> הוא <math>\operatorname{tr}\!\left(A_G^t\right)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).		* מספר ההילוכים הסגורים מאורך <math>t</math> ב־<math>G</math> הוא <math>\operatorname{tr}\!\left(A_G^t\right)</math> (כאשר שני הילוכים שמתחילים בנקודות שונות הם שונים גם אם הם עוברים על אותן נקודות).
	* אם <math>G,H</math> סופיים ולא מכוונים אז <math>\operatorname{~~spek~~}(G\times H)=\operatorname{spec}(G)+\operatorname{spec}(H)</math>.		* אם <math>G,H</math> סופיים ולא מכוונים אז <math>\operatorname{spec}(G\times H)=\operatorname{spec}(G)+\operatorname{spec}(H)</math>.
	* אם <math>G</math> גרף <math>d</math>־רגולרי אז <math>d\in\operatorname{spec}(G)</math> וו״ע מתאימים הם <math>v_A=(I_A(i))_{i=1}^~~{\|V(G)\|}~~</math> לכל רכיב קשירות <math>A\subseteq V(G)</math>.		* אם <math>G</math> גרף <math>d</math>־רגולרי אז <math>d\in\operatorname{spec}(G)</math> וו״ע מתאימים הם <math>v_A=(I_A(v_i))_{i=1}^n</math> לכל רכיב קשירות <math>A\subseteq V(G)=\{v_i\}_{i=1}^n</math>.
	* יהא <math>G</math> סופי ולא מכוון. <math>G</math> דו־צדדי אם״ם מתקיים התנאי הבא: <math>\lambda</math> ע״ע של <math>A_G</math> מריבוי אלגברי <math>k</math> אם״ם <math>-\lambda</math> ע״ע מאותו ריבוי.		* יהא <math>G</math> סופי ולא מכוון. <math>G</math> דו־צדדי אם״ם מתקיים התנאי הבא: <math>\lambda</math> ע״ע של <math>A_G</math> מריבוי אלגברי <math>k</math> אם״ם <math>-\lambda</math> ע״ע מאותו ריבוי.
	* הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.		* הלפלסיאנים של שני גרפים זהים אם״ם יש להם תתי־גרפים פורשים איזומורפיים.

אור שחף: /* סוגי גרפים נפוצים */

2013-02-12T20:15:07Z

סוגי גרפים נפוצים

→ הגרסה הקודמת		גרסה מ־20:15, 12 בפברואר 2013
שורה 28:		שורה 28:
	** '''מותן (girth)''' של גרף <math>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.		** '''מותן (girth)''' של גרף <math>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.
	* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.		* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
	** '''גרף {{ltr\|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו ~~הדרגה היוצאת~~ של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.		** '''גרף {{ltr\|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו דרגת החוץ של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.
	* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=V^1\uplus V^2</math> כך ש־<math>E(G)\subseteq V^1\times V^2</math>.		* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=V^1\uplus V^2</math> כך ש־<math>E(G)\subseteq V^1\times V^2</math>.
	** '''גרף דו־צדדי מלא''' <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V^1\uplus V^2</math> (כאשר <math>\left\|V^1\right\|=n,\left\|V^2\right\|=m</math>) וצלעותיו <math>V^1\times V^2</math>.		** '''גרף דו־צדדי מלא''' <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V^1\uplus V^2</math> (כאשר <math>\left\|V^1\right\|=n,\left\|V^2\right\|=m</math>) וצלעותיו <math>V^1\times V^2</math>.

אור שחף: /* תורת הגרפים האלגברית */

2013-02-12T20:09:27Z

תורת הגרפים האלגברית

→ הגרסה הקודמת		גרסה מ־20:09, 12 בפברואר 2013
שורה 140:		שורה 140:
	* '''מטריצת השכנות''' של גרף סופי <math>G</math> (מכוון או לא) כך ש־<math>V=\{v_i\}_{i=1}^n</math> היא <math>A_G\in\mathbb N_0^{n\times n}</math> שבה <math>a_{ij}</math> הוא מספר הצלעות מ־<math>v_i</math> ל־<math>v_j</math>.		* '''מטריצת השכנות''' של גרף סופי <math>G</math> (מכוון או לא) כך ש־<math>V=\{v_i\}_{i=1}^n</math> היא <math>A_G\in\mathbb N_0^{n\times n}</math> שבה <math>a_{ij}</math> הוא מספר הצלעות מ־<math>v_i</math> ל־<math>v_j</math>.
	* נסמן <math>\operatorname{spec}(A_G)=\operatorname{spec}(G)</math> כרב־קבוצה של הע״ע של <math>A_G</math> (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו).		* נסמן <math>\operatorname{spec}(A_G)=\operatorname{spec}(G)</math> כרב־קבוצה של הע״ע של <math>A_G</math> (כאשר כל ע״ע מופיע בריבוי השווה לריבוי האלגברי שלו).
	* '''מטריצת הדרגות''' של גרף <math>G</math> מסדר <math>n</math> שקודקודיו <math>V(G)=\{v_i\}_{i=1}^n</math> ~~הוא~~ המטריצה <math>D_G:=\Big(\delta_{ij}d_G(v_i)\Big)_{i,j=1}^n</math>.		* '''מטריצת הדרגות''' של גרף <math>G</math> מסדר <math>n</math> שקודקודיו <math>V(G)=\{v_i\}_{i=1}^n</math> היא המטריצה <math>D_G:=\Big(\delta_{ij}d_G(v_i)\Big)_{i,j=1}^n</math>.
	* '''הלפלסיאן''' של <math>G</math> הוא <math>L_G:=D_G-A_G</math>.		* '''הלפלסיאן''' של <math>G</math> הוא <math>L_G:=D_G-A_G</math>.

אור שחף: /* סוגי גרפים נפוצים */

2013-02-12T20:08:21Z

סוגי גרפים נפוצים

→ הגרסה הקודמת		גרסה מ־20:08, 12 בפברואר 2013
שורה 22:		שורה 22:
	* '''גרף ריק''' <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.		* '''גרף ריק''' <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.
	* '''גרף מלא/שלם''' <math>K_n</math> הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.		* '''גרף מלא/שלם''' <math>K_n</math> הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.
	-** '''קליקה''' בגרף היא תת־גרף מלא.		** '''קליקה''' בגרף היא תת־גרף מלא.
	-** '''מספר הקליקה''' של גרף <math>G</math> מסומן <math>\omega(G)</math> ושווה לסדר המקסימלי של קליקה ב־<math>G</math>.		** '''מספר הקליקה''' של גרף <math>G</math> מסומן <math>\omega(G)</math> ושווה לסדר המקסימלי של קליקה ב־<math>G</math>.
	* '''מסילה''' <math>P_n</math> היא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):\ 1\le i<n\}</math>.		* '''מסילה''' <math>P_n</math> היא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):\ 1\le i<n\}</math>.
	* '''מעגל''' <math>C_n</math> (<math>n\ge3</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):\ 1\le i<n\}\cup\{(v_n,v_1)\}</math>.		* '''מעגל''' <math>C_n</math> (<math>n\ge3</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):\ 1\le i<n\}\cup\{(v_n,v_1)\}</math>.
	-** '''מותן (girth)''' של גרף <math>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.		** '''מותן (girth)''' של גרף <math>G</math> הוא אורך המעגל הקטן ביותר בגרף, ומסומן <math>g(G)</math>. אם אין בגרף מעגלים (יער) אז <math>g(G)=\infty</math>.
	* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.		* '''גרף ''d''־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
	** '''גרף {{ltr\|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.		** '''גרף {{ltr\|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.

אור שחף: /* סוגי גרפים נפוצים */

2013-02-12T20:06:59Z

סוגי גרפים נפוצים

→ הגרסה הקודמת		גרסה מ־20:06, 12 בפברואר 2013
שורה 30:		שורה 30:
	** '''גרף {{ltr\|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.		** '''גרף {{ltr\|''d<sup>+</sup>''}}־רגולרי''' הוא גרף מכוון שבו הדרגה היוצאת של כל קודקוד היא <math>d</math>. באותו אופן מגדירים גרף <math>d^-</math>־רגולרי.
	* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=V^1\uplus V^2</math> כך ש־<math>E(G)\subseteq V^1\times V^2</math>.		* '''גרף דו־צדדי (דו״צ)''' הוא גרף פשוט <math>G</math> שבו קיימת חלוקה <math>V(G)=V^1\uplus V^2</math> כך ש־<math>E(G)\subseteq V^1\times V^2</math>.
	** '''גרף דו־צדדי מלא''' <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V^1\uplus V^2</math> (כאשר <math>\left\|V^1\right\|=n,\left\|U^2\right\|=m</math>) וצלעותיו <math>V^1\times V^2</math>.		** '''גרף דו־צדדי מלא''' <math>K_{m,n}</math> הוא הגרף שקודקודיו הם <math>V^1\uplus V^2</math> (כאשר <math>\left\|V^1\right\|=n,\left\|V^2\right\|=m</math>) וצלעותיו <math>V^1\times V^2</math>.
	** '''גרף ''r''־צדדי''' הוא גרף <math>G</math> בו יש חלוקה <math>V(G)=\biguplus_{i=1}^r V^i</math> ל־<math>r</math> תתי־קבוצות כך שלכל <math>i</math> הקודקודים ב־<math>V^i</math> אינם שכנים, כלומר <math>E(G)\subseteq\bigcup_{i\ne j}V^i\times V^j</math>.		** '''גרף ''r''־צדדי''' הוא גרף <math>G</math> בו יש חלוקה <math>V(G)=\biguplus_{i=1}^r V^i</math> ל־<math>r</math> תתי־קבוצות כך שלכל <math>i</math> הקודקודים ב־<math>V^i</math> אינם שכנים, כלומר <math>E(G)\subseteq\bigcup_{i\ne j}V^i\times V^j</math>.
	** '''גרף ''r''־צדדי מלא''' הוא גרף <math>r</math>־צדדי <math>G</math> בו <math>E(G)=\bigcup_{i\ne j}V^i\times V^j</math>, כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.		** '''גרף ''r''־צדדי מלא''' הוא גרף <math>r</math>־צדדי <math>G</math> בו <math>E(G)=\bigcup_{i\ne j}V^i\times V^j</math>, כלומר שני קודקודים הם שכנים אם״ם הם נמצאים בצדדים שונים.

אור שחף ב־20:04, 12 בפברואר 2013

2013-02-12T20:04:42Z

הצגת שינויים