צומת (תורת הגרפים)

גרף לא מכוון בעל 6 קודקודים ו-7 קשתות

בתורת הגרפים, קודקוד (באנגלית: Vertex) הוא יחידת היסוד ממנה מורכב גרף. במדעי המחשב מקובל גם המונח "צומת". מקובל לסמן קודקוד כלשהו באות (הקטנה) $v$.

קודקודים וצלעות

צלע היא זוג קודקודים, כאשר צלע לא מכוונת היא קבוצה בגודל 2 (זוג לא סדור), ואילו צלע מכוונת זוג סדור של קודקודים. כל גרף מורכב מקבוצת הקודקודים שלו המסומנת באות $V$, ומקבוצת הצלעות שלו המסומנת באות $E$, כאשר $E\subseteq {\tbinom {[V]}{2}}$ (כלומר: כל צלע בגרף מכילה אך ורק קודקודים המשתייכים לקבוצת הקודקודים של אותו גרף). גרף שכל צלעותיו אינן מכוונות נקרא "גרף לא מכוון", בעוד שגרף שכל צלעותיו מכוונות נקרא "גרף מכוון".

שכנים של קודקוד

קודקוד $u$ נקרא "שכן" של קודקוד $v$ אם $\{v,u\}\in E$ (כלומר הצלע ה"מחברת" בין שניהם שייכת לקבוצת הצלעות של הגרף). בגרף לא מכוון, שבו הצלעות הן קבוצות לא סדורות, היות שלכל $v,u$ מתקיים $\{u,v\}=\{v,u\}$, מתקיים שאם $\{v,u\}\in E$ אזי גם $\{u,v\}\in E$. לכן לכל שני קודקודים $v,u$ ב- $V$ מתקיים שאם $u$ שכן של $v$ אזי גם $v$ שכן של $u$.

לכל קודקוד $v$ בגרף, קבוצת כל השכנים שלו בגרף מסומנת: $N(v)$, ובאופן פורמלי: $N(v)=\{u\in V\|\{v,u\}\in E\}$.

ערכיות (דרגה) של קודקוד

בגרף לא מכוון, ערכיות (דרגה) של קודקוד $v$ היא מספר השכנים שלו בגרף, והיא מסומנת: $d(v)$. באופן פורמלי: $d(v)=|N(v)|$.

בגרף מכוון, דרגת הכניסה של קודקוד שווה למספר הצלעות ה"נכנסות" אליו, ודרגת היציאה שווה למספר הצלעות ה"יוצאות" ממנו.

גרף n-צביע הוא גרף הניתן לצביעה ב-n צבעים כך שכל שני קודקודים שכנים צבועים בצבע שונה.

קישורים חיצוניים

מדיה וקבצים בנושא צומת בוויקישיתוף

• צומת, באתר MathWorld (באנגלית)

ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.