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

מתוך המכלול, האנציקלופדיה היהודית
קפיצה לניווט קפיצה לחיפוש
גרף לא מכוון בעל 6 קודקודים ו-7 קשתות

בתורת הגרפים, צומת או קודקודאנגלית: Vertex) הוא יחידת היסוד ממנה מורכב הגרף. קבוצת הקודקודים בגרף מסומנת באות .

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

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

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

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

  • צומת, באתר MathWorld (באנגלית)   המזהה לא מולא ולא נמצא בוויקינתונים, נא למלא את הפרמטר.
P mathematics.svg ערך זה הוא קצרמר בנושא מתמטיקה. אתם מוזמנים לתרום למכלול ולהרחיב אותו.
סמל המכלול גמרא 2.PNG
הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0