זוג $G=(V,E)$ של קבוצת צמתים $\emptyset \neq V=\left\{ u_{1},u_{2},u_{3},\dots \right\}$ וקבוצת קשתות $E=\left\{ e_{1},e_{2},e_{3},\dots \right\}$ כאשר לכל קשת מוגדרים שני קצוות יקרא גרף.
נסמן קשת ואת שתי קצוותיה כך $u_{1} \overset{e_{1}}{-}u_{4}$ ונאמר $e_{1}$ מחברת בין $u_{1}$ ח-$u_{4}$ וכי $u_{1},u_{4}$ סמוכים או שכנים.

מספר הפעמים שהצומת מופיע כקצה קשת יקרא דרגת הצומת.

או: $d(u_{8})=3,d(u_{3})=2,\dots$.

סכום הדרגות שווה פעמיים מספר הקשתות:

מספר הצמתים עם דרגה אי-זוגית הוא זוגי

גרף שאין בו קשתות מקבילות או חוגים עצמיים יקרא גרף פשוט.

בגרף פשוט $|E|\leq \begin{pmatrix}|V|\\2\end{pmatrix}$

בין צומת $u$ לצומת $v$ קיים מסלול המוגדר:

כאשר $v_{i-1}\overset{e_{i}}{-}v_{i}\in E$.

​

מספר הקשתות במסלול יקרא אורך מסלול ויסומן ב-$\ell$.
מסלול באורך 0 הוא צומת אחד ללא קשתות.

מסלול באורך חיובי מהצורה $v_{0}\overset{e_{1}}{-}v_{1}\overset{e_{2}}{-}v_{2}\overset{e_{3}}{-}\dots \overset{e_{\ell-1}}{-}v_{\ell-1}\overset{e_{\ell}}{-}v_{\ell}=v_{0}$.

מסלול $v_{0}\overset{e_{1}}{-}v_{1}\overset{e_{2}}{-}v_{2}\overset{e_{3}}{-}\dots \overset{e_{\ell-1}}{-}v_{\ell-1}\overset{e_{\ell}}{-}v_{\ell}$ יקרא פשוט אם $v_{0},\dots,v_{\ell}$ שונים ולכן גם $e_{1},\dots,e_{\ell}$ שונות.

מעגל $v_{0}\overset{e_{1}}{-}v_{1}\overset{e_{2}}{-}v_{2}\overset{e_{3}}{-}\dots \overset{e_{\ell-1}}{-}v_{\ell-1}\overset{e_{\ell}}{-}v_{0}$ יקרא פשוט אם $v_{0},\dots,v_{\ell-1}$ שונים ולכן גם $e_{1},\dots,e_{\ell-1}$ שונות.

קיום מעגל אינו גורר קיום מעגל פשוט.

קיים מסלול בגרף מ-$u$ ל-$v$ אם ורק אם קיים בגרך מסלול פשוט מ-$u$ ל-$v$.

גרף $G=(V,E)$ נקרא קשיר אם קיים מסלול בין כל שני צמתים בו.

יהי גרף $G=(V,E)$.
נקרא לתת קבוצה $S$ של קבוצת הצמתים $V$ חתך.

קשת $e$ חוצה את החתך $S$ אם קצה אחד של $e$ נמצא ב-$S$ והקצה השני מחוץ ל-$S$.

חתך $S$ ייקרא לא טריוויאלי אם $S \neq \emptyset$ וגם $V \setminus S \neq \emptyset$.

גרף הוא קשיר $\iff$ לכל חתך לא טריוויאלי יש לפחות קשת אחת חוצה.

גרף $G=(V,E)$ בעל קבוצת צמתים $V$ וקבוצת קשתות $E$ כך שלכל קשת מוגדרים מקור ויעד יקרא מכוון.
נסמן קשת עם מקור ויעד כך: $u_{4} \xrightarrow{e_{1}}u_{1}$.

​
​

גרף מכוון שאין בו קשתות מקבילות או חוגים עצמיים יקרא פשוט.

בגרף מכוון פשוט $|E|\leq |V|(|V|-1)$.

כמות הקשתות ש-$u$ הוא המקור שלהן תהיה דרגת היציאה של $u$.

כמות הקשתות ש-$u$ הוא היעד שלהן יקרא דרגת הכניסה של $u$.

מסלול מצומת $u$ לצומת $v$ המוגדר $u=v_{0}\xrightarrow{e_{1}}v_{1}\xrightarrow{e_{2}}v_{2}\xrightarrow{e_{3}}\dots \xrightarrow{e_{\ell-1}}v_{\ell-1}\xrightarrow{e_{\ell}}v_{\ell}$.
כאשר $v_{i-1}\xrightarrow{e_{i}}v_{i}\in E$.

מסלול באורך חיובי מהצורה $v_{0}\xrightarrow{e_{1}}v_{1}\xrightarrow{e_{2}}v_{2}\xrightarrow{e_{3}}\dots \xrightarrow{e_{\ell-1}}v_{\ell-1}\xrightarrow{e_{\ell}}v_{0}$

מוגדרים בדומה להגדרות עבור גרף לא מכוון

קיים בגרף מעגל מכוון $\iff$ קיים בגרף מעגל מכוון פשוט

גרף מכוון נקרא קשיר היטב אם לכל שני צמתים $u$ ו-$v$ בו קיים מסלול מכוון מ-$u$ ל-$v$.

​

אם גרף מכוון $G$ קשיר היטב אזי גרף התשתיות של $G$ קשיר.

אם גרף התשתיות של גרף מכוון $G$ קשיר, אזי $G$ אינו בהכרח קשיר היטב.

מסלול בגרף העובר בכל קשת בגרף בדיוק פעם אחת יקרא אויילרי.

מעגל בגרף העובר בכל קשת בגרף בדיוק פעם אחת יקרא אויילרי.

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

גרף שיש בו מעגל אויילרי יקרא גרף אויילרי-מעגלי.

​
​

גרף אויילרי חייב להיות קשיר (למעט צמתים מבודדים)

גרף קשיר(עם קשת אחת לפחות) הוא אויילרי מעגלי $\iff$ לכל הצמתים דרגה זוגית.

$P$ הוא מעגל. כלומר, $v_{\ell}=v_{0}$.

גרף קשיר (עם קשת אחת לפחות) הוא אויילרי אך אינו אויילרי מעגלי $\iff$ יש בדיוק שני צמתים שדרגרתם אי זוגית.

גרף מכוון שגרף התשתית שלו קשיר (עם קשת אחת לפחות) הוא אוילרי מעגלי $\iff$ לכל צומת $v$ מתקיים $d_{in}(v)=d_{out}(v)$.

גרף מכוון שגרף התשתית שלו קשיר (עם קשת אחת לפחות) הוא אוילרי אך אינו אויילרי מעגלי $\iff$

• קיים צומת $u$ שמקיים $d_{out}(u)=d_{in}(u)+1$
• קיים צומת $v$ שמקיים $d_{in}(v)=d_{out}(v)+1$
• לכל $w \not\in \left\{ u,v \right\}$ מתקיים $d_{in}(w)=d_{out}(w)$

עבור קבוצה סופית $\Sigma$ נבנה גרף לא מכוון באופן הבא:

• צמתיו הם כל $2^{|\Sigma|}$ תתי הקבוצות של $\Sigma$.
• קשתותיו הן כל הזוגות $\left\{ U,U' \right\}$ כאשר הקבוצה $U'$ שונה מ-$U$ בדיוק באיבר אחד.

​
נניח עבור $\Sigma=\left\{ 1,2,3,4 \right\}$ מתקבל:
​

נרצה לראות אם גרף כזה הוא אויילרי מעגלי.
נשים לב כי עבור הקבוצה $\Sigma=\left\{ a,b,c \right\}$ מתקיים כי הגרף אינו אויילרי מעגלי כי קיימת צומת לה מספר אי זוגי של קשתות.
לכן זה לא תמיד מתקיים אך קיימות קבוצות עבורן הוא כן אווילרי מעגלי (נניח $\Sigma=\left\{ a,b \right\}$)

קבוצה סופית של אותיות נקראת אלפבית.

סדרה של אותיות מאלבפבית $\Sigma$.

מספר האותיות במילה נקרא אורך המילה.

תהי סדרה מעל $\Sigma$ למילים באורך $n$:
סדרה $\sigma_{1}\sigma_{2}\sigma_{3}\dots\sigma_{\ell}$ באורך $\ell=|\Sigma|^n$ כך ש-

עבור $\Sigma=\left\{ 0,1 \right\}$ ו-$n=3$ נקבל: $0011101000$
עבור $\Sigma=\left\{ 0,1 \right\}$ ו-$n=5$ נקבל: $00000100011001010011101011011111$

גרף מכוון $(V,E)$ המוגדר עבור אלפבית $\Sigma$ בגודל $|\Sigma|=k$ וטבעי חיובי $n$ נקרא גרף דה ברויין אם

• קבוצת הצמתים $V$ היא קבוצת המילים $\sigma_{1}\sigma_{2}\dots\sigma_{n-1}$ באורך $n-1$ מעל $\Sigma$
• קבוצת הקשתות $E$ היא קבוצת המילים $\sigma_{1}\sigma_{2}\dots\sigma_{n}$ באורך $n$ מעל $\Sigma$.

נסמן את גרף דה ברויין $G_{k,n}$.

​

​

$d_{in}=d_{out}=k$ לכל צומת בגרף.

לכל $n$ ו-$k$ הגרף $G_{k,n}$ הוא אוילרי-מעגלי.

לכל אלפבית $\Sigma$ ולכל $n$ קיימת סדרת דה ברויין באורך $\ell=|\Sigma|^n$.

קיים מנעול לחיצות המורכב מעשר הספרות העשרוניות $0,1,2,\dots,9$ וניתן לפתיחה ע"י הקשת קוד בעל ארבע ספרות.
המנעול תמיד בודק את 4 הספרות האחרונות שהכנסנו.
נרצה לבדוק בכמה הקשות ניתן לפרוץ את המנעול. איך נעשה את זה?

באופן נאיבי, נחשבו כי בגלל שיש $10^4$ אפשרויות לקודים שונים שניתן להכניס אז סה"כ יש $4\cdot 10^4$ הקשות. אך זה לא באמת נכון. נראה עכשיו איך פותרים זאת כמו שצריך עם סדרת דה-ברויין.

נרצה ליצור סדרה שבה בכל חלון בגודל $4$ יופיע קוד שונה. זה יוליך אותנו ליצירת סדרת דה ברויין על $\Sigma=\left\{ 0,1,2,\dots,9 \right\}$ ו-$n=4$ באורך $10^4$ וכך ע"י הקשת $10^4+3$ הקשות נפרוץ את המנעול לאור הציקליות.