Skip to main content
SUPERVISOR
حسین حاجی ابوالحسن (استاد مشاور) بهناز عمومی (استاد راهنما)
 
STUDENT
Zeinab Maleki
زینب مالکی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Doctor of Philosophy (PhD)
YEAR
1388

TITLE

Set Intersection Representations of Graphs
Representation of graphs in addition to having many applications in computer science is a useful tool to study structure and properties of graphs. A basic representation for graphs is the set intersection representation in which an assignment of sets to vertices determines an edge between two vertices, if the intersection of the corresponding sets satisfies a certain given rule . In this thesis we aim to mainly investigate different type of intersection representations of graphs.
نمایش گراف‌ها علاوه‌براین که ابزار مفیدی برای مطالعه ساختار و خواص گراف‌ها هستند، در علوم کامپیوتر نظری نیز کاربردهای فراوانی دارند و همواره مورد توجه محققان قرار گرفته‌اند. یکی از روش‌های نمایش گراف که بیشترین توجه را به خود اختصاص داده، نمایش $L$-اشتراکی ‌است که $L\\subset \\{0,1,2,\\dots\\}$ تعیین کننده مجاورت و یا عدم مجاورت دو رأس در گراف است. به عبارتی، به هر رأس گراف یک مجموعه نسبت داده می‌شود به‌طوری که دو رأس مجاور هستند اگر و تنها اگر اندازه اشتراک مجموعه‌های نظیر آن‌ها متعلق به $L$ باشد. موضوع پژوهش در این رساله مطالعه انواع نمایش‌های اشتراکی گراف‌ها و یافتن ارتباط آن‌ها با سایر مفاهیم و پارامترها در نظریه گراف است. در این راستا ضمن معرفی انواع مهم نمایش‌های $L$-اشتراکی، کران‌های پایین مناسبی برای کمترین تعداد برچسب‌های لازم در نمایش‌های اشتراکی وابسته به $L$ های مختلف ارائه شده است. سپس به طور خاص، به نمایش‌های $L$-اشتراکی متناظر با $L = \\{1,2,\\dots\\}$ که با سایر مفاهیم در نظریه گراف مانند پوشش‌های خوشه‌ای یالی در ارتباط تنگاتنگ است، پرداخته شده و کران‌هایی به ویژه برای گراف‌های بدون $K_{1,3}$ ارائه شده است. همچنین نمایش ضرب نقطه‌ای به گراف‌های جهت‌دار تعمیم داده شده و مورد مطالعه قرار گرفته است. در پایان، یک روش جدید متقارن‌سازی با استفاده از برچسب‌گذاری رأس‌ها ارائه شده که به عنوان ابزاری برای حل مسائل اکسترمال قابل استفاده است.

ارتقاء امنیت وب با وف بومی