הצגת המקור של הדף "גרף פרש"

[[קובץ:Knight's graph showing number of possible moves.svg|ממוזער|גרף פרש עבור לוח רגיל. בתוך כל צומת רשומה ה[[דרגה (תורת הגרפים)|דרגה]] שלו.]]
'''גרף פרש''' הוא [[גרף (תורת הגרפים)|גרף]] ש[[צומת (תורת הגרפים)|צמתיו]] מייצגים משבצות של [[לוח שחמט]], ו[[קשת (תורת הגרפים)|קשת]]ותיו מייצגות מסעים חוקיים של [[פרש (שחמט)|פרש]] (כלומר שני קודקודים מחוברים [[אם ורק אם]] פרש יכול לעבור בצעד יחיד בין המשבצות שהם מייצגים).

עבור לוח בגודל mxn, יש בו <math>mn</math> צמתים ו-<math>4mn-6(m+n)+8</math> קשתות. עבור nxn יש בו <math>4(n-2)(n-1)</math> קשתות (שמונה פעמים [[מספר משולשי]]).

גרף כזה הוא [[גרף דו-צדדי|דו-צדדי]], מאחר שהוא [[צביעת גרף|2-צביע]] - צביעת לוח שחמט רגילה. משום כך הוא גם [[גרף מושלם]].

[[חידת מסע הפרש]] שואלת על מציאת [[מסלול המילטוני]] בגרף כזה.

==קישורים חיצוניים==
* {{MathWorld|KnightGraph}}

[[קטגוריה:תורת הגרפים]]