שינויים
יסודר ויורחב בהמשך
== הגדרות ==
* '''גרף''' הוא זוג <math>G=(V,E)</math> כך ש־<math>V</math> קבוצת קודקודים (נקראים גם "צמתים") ו־<math>E</math> רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
* '''לולאה''' היא צלע <math>(v,v)</math> כאשר <math>v\in V</math>.
* '''גרף פשוט''' הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־<math>E</math>).
* '''גרף מכוון''' הוא גרף בו הצלעות הן זוגות סדורים.
* '''גרף סופי''' הוא גרף בו <math>|V|,|E|<\infty</math>.
* '''סדר''' של גרף הוא מספר הקודקודים בו, כלומר <math>|V|</math>. לעתים מסומן <math>n(G)</math>.
* '''מידה''' של גרף היא מספר הצלעות – <math>|E|</math>. לעתים מסומנת <math>e(G)</math> או <math>m(G)</math>.
* '''דרגה''' של קודקוד <math>v\in V</math> היא מספר הצלעות העוברות בו. מסומנת <math>d(v)</math> או <math>d_G(v)</math>.
** מתקיים <math>\sum_{v\in V}d_G(v)=2|E|</math>.
* '''איחוד''' של גרפים פשוטים <math>G,H</math> הוא <math>G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big)</math>. באותו אופן מוגדר איחוד זר.
=== סוגים נפוצים ===
* '''גרף ריק''' מסדר <math>n</math> מסומן <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.
* '''גרף מלא/שלם''' מסדר <math>n</math> (<math>K_n</math>) הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.
* '''מסילה''' מסדר <math>n</math> (<math>P_n</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):i\in[1,n-1]\cap\mathbb N\}</math>.
* '''מעגל''' מסדר <math>n>2</math> (<math>C_n</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):i\in[1,n-1]\cap\mathbb N\}\cup\{(v_n,v_1)\}</math>.
* '''גרף <math>d</math>־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
** גרף הוא ריק אם״ם הוא 0־רגולרי.
** גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
** גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
** אם גרף סופי ופשוט הוא <math>d</math>־רגולרי כך ש־<math>d</math> אי־זוגי אזי הגרף מסדר זוגי.
* '''יער''' הוא גרף פשוט ללא מעגלים.
** '''עץ''' הוא יער קשיר.
=== הילוכים ===
* '''הילוך''' בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה <math>v_0,v_1,\dots,v_n</math> כך ש־<math>\forall i:\ (v_i,v_{i+1})\in E</math>.
** אורך ההילוך הוא <math>n</math> – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
** ההילוך '''סגור''' אם <math>v_0=v_n</math>.
* '''מסלול''' הוא הילוך שבו אין צלעות חוזרות.
* '''מסילה''' היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
** כל מסילה היא מסלול.
* קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
* '''רכיב קשירות''' בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות <math>\rightarrow</math> המקיים <math>u\rightarrow v</math> אם״ם יש מסילה בין <math>u,v</math>.
** מספר רכיבי הקשירות בגרף <math>G</math> יסומן <math>K(G)</math>.
** '''גרף קשיר''' הוא גרף שבו יש מחלקת שקילות אחת.
*** גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
=== תתי גרפים ===
* '''השמטת צלע''' <math>e\in E</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{e\}:=(V,E\setminus\{e\})</math>.
* '''השמטת קודקוד''' <math>v\in V</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\})</math>.
* '''תת־גרף''' הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
** '''תת־גרף פורש''' הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד.
** '''תת־גרף מושרה''' הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.
*** אם <math>H</math> תת־גרף מושרה של <math>G</math> אזי <math>\forall u,v\in V(H):\ \Big((u,v)\in E(G)\iff(u,v)\in E(H)\Big)</math>. כלומר, כל שני קודקודים שכנים ב־<math>H</math> הם שכנים ב־<math>G</math>.
* '''גרף''' הוא זוג <math>G=(V,E)</math> כך ש־<math>V</math> קבוצת קודקודים (נקראים גם "צמתים") ו־<math>E</math> רב קבוצה של זוגות לא סדורים של קודקודים (הזוגות נקראים "צלעות" או "קשתות").
* '''לולאה''' היא צלע <math>(v,v)</math> כאשר <math>v\in V</math>.
* '''גרף פשוט''' הוא גרף ללא לולאות וללא ריבוי צלעות (כלומר, אף צלע לא מופיע פעמיים ב־<math>E</math>).
* '''גרף מכוון''' הוא גרף בו הצלעות הן זוגות סדורים.
* '''גרף סופי''' הוא גרף בו <math>|V|,|E|<\infty</math>.
* '''סדר''' של גרף הוא מספר הקודקודים בו, כלומר <math>|V|</math>. לעתים מסומן <math>n(G)</math>.
* '''מידה''' של גרף היא מספר הצלעות – <math>|E|</math>. לעתים מסומנת <math>e(G)</math> או <math>m(G)</math>.
* '''דרגה''' של קודקוד <math>v\in V</math> היא מספר הצלעות העוברות בו. מסומנת <math>d(v)</math> או <math>d_G(v)</math>.
** מתקיים <math>\sum_{v\in V}d_G(v)=2|E|</math>.
* '''איחוד''' של גרפים פשוטים <math>G,H</math> הוא <math>G\cup H:=\Big(V(G)\cup V(H),E(G)\cup E(H)\Big)</math>. באותו אופן מוגדר איחוד זר.
=== סוגים נפוצים ===
* '''גרף ריק''' מסדר <math>n</math> מסומן <math>N_n</math> הוא הגרף שסדרו <math>n</math> ומידתו 0.
* '''גרף מלא/שלם''' מסדר <math>n</math> (<math>K_n</math>) הוא הגרף שסדרו <math>n</math> ובין כל שני קודקודים יש צלע אחת בדיוק.
* '''מסילה''' מסדר <math>n</math> (<math>P_n</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):i\in[1,n-1]\cap\mathbb N\}</math>.
* '''מעגל''' מסדר <math>n>2</math> (<math>C_n</math>) הוא הגרף שסדרו <math>n</math> ושניתן לסדר את קודקודיו כ־<math>v_1,\dots,v_n</math> ואז <math>E=\{(v_i,v_{i+1}):i\in[1,n-1]\cap\mathbb N\}\cup\{(v_n,v_1)\}</math>.
* '''גרף <math>d</math>־רגולרי''' הוא גרף שבו דרגת כל קודקוד היא <math>d</math>.
** גרף הוא ריק אם״ם הוא 0־רגולרי.
** גרף 1־רגולרי ופשוט הוא איחוד זר של צלעות.
** גרף 2־רגולרי ופשוט הוא איחוד זר של מעגלים.
** אם גרף סופי ופשוט הוא <math>d</math>־רגולרי כך ש־<math>d</math> אי־זוגי אזי הגרף מסדר זוגי.
* '''יער''' הוא גרף פשוט ללא מעגלים.
** '''עץ''' הוא יער קשיר.
=== הילוכים ===
* '''הילוך''' בגרף הוא סדרת קודקודים (חזרות מותרות) כך שכל קודקוד שכן של הסמוכים לו. כלומר, זו סדרה <math>v_0,v_1,\dots,v_n</math> כך ש־<math>\forall i:\ (v_i,v_{i+1})\in E</math>.
** אורך ההילוך הוא <math>n</math> – מספר הצלעות שבו, כלומר מספר הקודקודים פחות 1.
** ההילוך '''סגור''' אם <math>v_0=v_n</math>.
* '''מסלול''' הוא הילוך שבו אין צלעות חוזרות.
* '''מסילה''' היא הילוך שבו אין קודקודים חוזרים, למעט אם הקודקוד הראשון שווה לקודקוד האחרון.
** כל מסילה היא מסלול.
* קיים הילוך בין שני קודקודים אם״ם קיימת מסילה בינהם.
* '''רכיב קשירות''' בגרף לא מכוון הוא מחלקת שקילות של יחס השקילות <math>\rightarrow</math> המקיים <math>u\rightarrow v</math> אם״ם יש מסילה בין <math>u,v</math>.
** מספר רכיבי הקשירות בגרף <math>G</math> יסומן <math>K(G)</math>.
** '''גרף קשיר''' הוא גרף שבו יש מחלקת שקילות אחת.
*** גרף הוא קשיר אם״ם הוא אינו איחוד זר של שני גרפים.
=== תתי גרפים ===
* '''השמטת צלע''' <math>e\in E</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{e\}:=(V,E\setminus\{e\})</math>.
* '''השמטת קודקוד''' <math>v\in V</math> מגרף <math>G</math> היא הפיכת הגרף ל־<math>G\setminus\{v\}:=(V\setminus\{v\},E\setminus\{(v,u):\ u\in V\})</math>.
* '''תת־גרף''' הוא הגרף המתקבל מסדרה של השמטות קודקודים ו/או צלעות.
** '''תת־גרף פורש''' הוא תת־גרף המתקבל מסדרה של השמטות צלעות בלבד.
** '''תת־גרף מושרה''' הוא תת־גרף המתקבל מסדרה של השמטות קודקודים בלבד.
*** אם <math>H</math> תת־גרף מושרה של <math>G</math> אזי <math>\forall u,v\in V(H):\ \Big((u,v)\in E(G)\iff(u,v)\in E(H)\Big)</math>. כלומר, כל שני קודקודים שכנים ב־<math>H</math> הם שכנים ב־<math>G</math>.
