Graphs are mathematical structures consisting of nodes connected by edges, used to model pairwise relations between objects.الغراف هو هيكل رياضي يتكون من رؤوس (vertices) وحواف (edges) تربط بينها. على عكس الخريطة الجغرافية، المهم هنا ليس شكل الخطوط، بل وجود الرابطة بحد ذاتها وربما وزنها (weight) (مثل طول الطريق أو زمن السفر). يتيح هذا التجريد تطبيق خوارزميات البحث نفسها على الشبكات الاجتماعية، وتدفقات المرور، وحتى سلاسل التفاعلات الكيميائية.
يرتبط نشأة نظرية الغرافات بعمل ليونارد أويلر 'حل مشكلة تتعلق بهندسة الموضع' (1736)، حيث أظهر استحالة عبور جميع جسور كونيغسبرغ السبعة دون المرور بأحدها مرتين. قدم المصطلح 'غراف' ك. كونيغ في عام 1936. في القرن العشرين، تطورت نظرية الغرافات بسرعة بفضل مسائل الاستمثال المتقطع والمعلوماتية.
تُمثّل الغرافات أنظمة التفاعلات الزوجية. يعتمد التحليل على مصفوفات المجاورة (adjacency matrices) والوقوع (incidence matrices). تُدرس خصائص الغرافات من خلال الثوابت: الاتصالية (connectivity)، العدد الدوراني (cyclomatic number)، العدد اللوني (chromatic number). تعتمد الخوارزميات الفعالة على الغرافات (إيجاد أقصر طريق، وأقصى تدفق) على طرق البرمجة الديناميكية (dynamic programming) والاستراتيجيات الجشعة (greedy strategies). في الفيزياء، تُطبق الغرافات في تقنية المخططات (مخططات فاينمان (Feynman diagrams) هي غرافات موجهة) وفي دراسة الأوساط العشوائية.
تساعد الغرافات في إيجاد أقصر طريق في جهاز الملاحة والتوصية بأصدقاء جدد في الشبكات الاجتماعية.
في الغراف الاجتماعي لفيسبوك، بين أي مستخدمين يوجد في المتوسط 3.5 خطوة فقط - وهذا ما يسمى 'نظرية الست مصافحات' عملياً.





















