צומת (תורת הגרפים) – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט: החלפת טקסט אוטומטית (-{{תבנית: +{{) |
מ תמונות - הסבה לעברית, תיקון פרמטרים# |
||
שורה 1: | שורה 1: | ||
[[ |
[[קובץ:6n-graf.svg|שמאל|ממוזער|גרף לא מכוון בעל 6 קודקודים ו-7 קשתות]] |
||
ב[[תורת הגרפים]], '''צומת''' או '''קודקוד''' (ב[[אנגלית]]: '''vertex''') הוא יחידת היסוד ממנה מורכב ה[[גרף (תורת הגרפים)|גרף]]. גרף לא מכוון מורכב מזוגות לא סדורים של קודקודים, וגרף מכוון מורכב מ[[זוג סדור|זוגות סדורים]] של קודקודים (כלומר, יש משמעות לכיוון של הקשתות המחברות את הקודקודים. כל קשת יוצאת מקודקוד אחד ונכנסת לקודקוד שני). |
ב[[תורת הגרפים]], '''צומת''' או '''קודקוד''' (ב[[אנגלית]]: '''vertex''') הוא יחידת היסוד ממנה מורכב ה[[גרף (תורת הגרפים)|גרף]]. גרף לא מכוון מורכב מזוגות לא סדורים של קודקודים, וגרף מכוון מורכב מ[[זוג סדור|זוגות סדורים]] של קודקודים (כלומר, יש משמעות לכיוון של הקשתות המחברות את הקודקודים. כל קשת יוצאת מקודקוד אחד ונכנסת לקודקוד שני). |
||
גרסה מ־22:10, 23 באוקטובר 2016
בתורת הגרפים, צומת או קודקוד (באנגלית: vertex) הוא יחידת היסוד ממנה מורכב הגרף. גרף לא מכוון מורכב מזוגות לא סדורים של קודקודים, וגרף מכוון מורכב מזוגות סדורים של קודקודים (כלומר, יש משמעות לכיוון של הקשתות המחברות את הקודקודים. כל קשת יוצאת מקודקוד אחד ונכנסת לקודקוד שני).
דרגה של קודקוד בגרף לא מכוון שווה למספר הקשתות המחברות אותו עם קודקודים אחרים. בגרף מכוון, דרגת הכניסה של קודקוד שווה למספר הקשתות הנכנסות אליו, ודרגת היציאה שווה למספר הקשתות היוצאות ממנו.
גרף k - צביע הוא גרף הניתן לצביעה ב k צבעים כך שכל שני צמתים המחוברים בקשת צבועים בצבע שונה.
קבוצת הקודקודים בגרף מסומנת באות .
נושאים בתורת הגרפים | ||
---|---|---|
הגדרות | צומת • קשת • דרגה • מסלול • מרחק | |
מבנים | גרף • גרף ממושקל • מעגל • גרף מקרי • היפרגרף • מולטיגרף • עץ • קומפלקס | |
בניות וטיפוסים | גרף משלים • גרף קיילי • גרף שלם • גרף תחרות • עץ פורש • רשת זרימה • שידוך | |
תכונות | גרף n-צביע • גרף דו-צדדי • גרף מישורי • גרף מרחיב • גרף רגולרי • גרף קשיר • עץ בינומי • עץ פורש מינימלי |