![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Knight%2527s_graph_showing_number_of_possible_moves.svg/langhe-640px-Knight%2527s_graph_showing_number_of_possible_moves.svg.png&w=640&q=50)
גרף פרש
ויקיפדיה האנציקלופדיה encyclopedia
גרף פרש הוא גרף שצמתיו מייצגים משבצות של לוח שחמט, וקשתותיו מייצגות מסעים חוקיים של פרש (כלומר שני קודקודים מחוברים אם ורק אם פרש יכול לעבור בצעד יחיד בין המשבצות שהם מייצגים).
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Knight%27s_graph_showing_number_of_possible_moves.svg/640px-Knight%27s_graph_showing_number_of_possible_moves.svg.png)
עבור לוח בגודל mxn, יש בו צמתים ו-
קשתות. עבור nxn יש בו
קשתות (שמונה פעמים מספר משולשי).
גרף כזה הוא דו-צדדי, מאחר שהוא 2-צביע - צביעת לוח שחמט רגילה. משום כך הוא גם גרף מושלם.
חידת מסע הפרש שואלת על מציאת מסלול המילטוני בגרף כזה.