הבדלים בין גרסאות בדף "תורת הגרפים"

נוספו 2 בתים ,  לפני 3 שנים
מ
בוט החלפות: לעיתים
מ (בוט: החלפת טקסט אוטומטית (-חברתיות +חברתיות))
מ (בוט החלפות: לעיתים)
'''גרף מכוון''' (directed graph, digraph) הוא [[קבוצה (מתמטיקה)|קבוצה]] של '''צמתים''' (נקראים גם נקודות, קודקודים, nodes, vertices) וקבוצה של '''קשתות מכוונות''' (directed edges, arcs). כאשר ישנה משמעות לכיוונה של קשת מכוונת - היא יוצאת מצומת אחד ונכנסת לצומת אחר. באופן פורמלי, גרף מכוון <math>\ D</math> מוגדר על ידי <math>\ (V,E)</math> כאשר <math>\ V</math> היא קבוצת הצמתים ו-<math>\ E \subseteq V \times V</math> היא קבוצת הקשתות. קשת <math>\ e=(u,v)\in E</math> יוצאת מ-<math>\ u </math> ונכנסת ל-<math>\ v</math>.
 
'''גרף בלתי מכוון''' (undirected graph), ולעתיםולעיתים בפשטות '''גרף''' הוא קבוצה של צמתים וקבוצה של '''קשתות''' (edges). כל קשת מקשרת בין שני צמתים. באופן פורמלי, גרף בלתי מכוון <math>\ G</math> מוגדר על ידי <math>\ (V,E)</math> כאשר <math>\ V</math> היא קבוצת הצמתים ו-<math>\ E \subseteq \{uv \mid u,v \in V\}</math> היא קבוצת הקשתות. ניתן לראות בגרפים בלתי מכוונים [[מקרה פרטי]] של גרפים מכוונים, בהם עבור כל זוג צמתים u ו-v, הקשתות מ-u ל-v ומ-v ל-u קיימות שתיהן, או חסרות שתיהן.
 
'''גרף סופי''' (finite graph) הוא גרף שקבוצת הצמתים שלו סופית. '''גרף אינסופי''' (infinite graph) הוא גרף שקבוצת הצמתים שלו היא [[אינסוף|אינסופית]].