کلیک (نظریه گراف)
در ریاضیات و در زمینه نظریه گراف کلیک (به انگلیسی: Clique)، برای گرافی بدون جهت زیرمجموعهای از رئوس که زیرگرافی کامل میسازند؛ به سخنی دیگر، هر جفت رأس همسایه بوده و میان هر جفت-رأس در یک کلیک یالی هست. شمار گرههای یک کلیک اندازهٔ کلیک نامیده میشود. گروهکها از مفهومهای بنیادی نظریه گراف هستند و کاربرد فراوانی در ریاضی و دانش رایانه دارند. گروهکی که نتوان آن را گستراند کلیک بیشین نامیده میشود. به سخنی دیگر، با افزودن هر گرهای به این کلیک، دستکم یک جفت-گرهٔ ناهمسایه خواهیم داشت و این کلیک زیرمجموعهای از گروهکی بزرگتر نیست. یافتن گروهکی بیشینه برای یک گراف پرسمان کلیک بیشینه نامیده میشود. این پرسمان انپی کامل است،[1]
دانش رایانه
برخی پرسمانهای کلیک عبارتند از:
- یافتن کلیک بیشین.
- فهرست همهٔ گروهکهای بیشین برای یک گراف.
- یافتن کلیک وزندار بیشینه در گرافی وزن دار.
- یافتن گروهکی بیشینه.
پیوند به بیرون
منابع
- The earlier work by Kuratowski (۱۹۳۰) characterizing گراف مسطحs by forbidden complete and complete bipartite subgraphs was originally phrased in topological rather than graph-theoretic terms.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.