משפט קירכהוף
משפט קירכהוף מסביר איך לחשב כמה עצים פורשים יש בגרף. מטריצה (טבלה של מספרים) חשובה כאן נקראת הלפלסיאן. הלפלסיאן L נוצרת מ־D - A. D היא טבלה עם דרגות הקודקודים על האלכסון. דרגה = כמה שכנים יש לקודקוד. A היא טבלת השכנויות, שמראה מי מחובר למי. ערכים עצמיים (מספרים מיוחדים של המטריצה) של הלפלסיאן אינם...
עץ פורש
עץ פורש הוא גרף שמכיל את כל הצמתים אבל אין בו מעגלים. (גרף = נקודות וקווים בין הנקודות.) אפשר לקבל עץ פורש על־ידי הסרת קווים ממעגלים עד שלא נשארים מעגלים. עץ פורש תמיד יש בו בדיוק N פחות 1 קווים, אם יש N נקודות. יש דרך מתמטית לספור כמה עצי פורש יש לגרף. במקרה שבו כל שתי נקודות מחוברות זו לזו, יש נ...