שינויים
/* מערכי תרגול */
[[88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11| עוד על גרפים]]
===שני התרגילים האחרונים בתרגול של אריאל===
א. מהו הקוטר המקסימלי של גרף קשיר עם <math>n</math> קודקודים?
ב. מהו המספר המינימלי של קשתות בגרף עם <math>n</math> קודקודים וקוטר 2?
פתרון:
א. <math>n-1</math>. לא יכול להיות יותר כי הקוטר מוגדר כמרחק המקסימלי בין קודקודים, ומרחק הוא אורך המסלול הקצר, ומסלול קצר לא מכיל מעגלים, ולכן מכיל לכל היותר <math>n</math> קודקודים, ולכן לכל היותר <math>n-1</math> קשתות. גרף קו הוא עם קוטר <math>n-1</math> כי זה המרחק בין הימני ביותר לשמאלי ביותר, לכן זה הקוטר המקסימלי.
ב. <math>n-1</math>. לא יכול להיות פחות כי אז הגרף לא יהיה קשיר וקטרו יהיה אינסוף ולא 2. גרף כוכב (יש קודקוד <math>u</math> המקיים <math>E=\{\{u,v\}:u\neq v\}</math> כלומר, הוא מחובר לכולם ואין עוד קשתות) הוא עם <math>n-1</math> קשתות וקוטר 2, כי המרחק בין שני קודקודים שאינם <math>u</math> הוא 2.
==תרגילי בית==
