بررسی بعد متریک همزمان خانواده گراف ها

بررسی بعد متریک همزمان خانواده گراف ها

محمداسماعیل نیکفر1

1) دکترای تخصصی ریاضی محض، دبیر ریاضی، آموزش وپرورش منطقه ۴، تهران، ایران

کد IOI مقاله : ADEZ-ACAEHB
محل انتشار : پایان نامه کارشناسی ارشد(pre-2392277)
چکیده :
    فرض کنید $G = (V, E)$ یک گراف همبند باشد. رأس $v \in V$ را رأس جداکننده، برای دو رأس $x$ و $y$ می‌نامیم، هرگاه $d_G(v, x) \neq d_G(v, y)$ و هر جفت از عناصر $G$ توسط حداقل یک عنصر از $S$ جدا شوند، مجموعه $S \subset V$ را مولدمتریک $^2$ $G$ می‌گوییم. کوچکترین مولدمتریک را پایه متریک $^3$ و اندازه پایه متریک را با نماد $\dim(G)$ نشان داده و آن را بعد متریک $^4$ می‌نامیم. برای هر خانواده $\mathcal{G} = \{G_1, G_2, \dots, G_k\}$ که روی مجموعه رؤوس شده‌اند، اگر $S \subset V$ به‌طور همزمان برای هر گرافی از این خانواده، مولدمتریک باشد، آنگاه $S$ را مولدمتریک همزمان $^5$ برای خانواده $\mathcal{G}$ می‌گوییم. کوچکترین مولدمتریک همزمان را پایه متریک همزمان $^6$ و اندازه آن را بعد متریک همزمان $^7$ می‌نامیم. ما در این رساله کران‌های دقیقی برای بعد متریک همزمان گراف‌ها بدست می‌آوریم. سپس به بررسی خانواده‌هایی از گراف‌ها پرداخته و برای بعد متریک همزمان آن‌ها مقدار یا کران دقیقی ارائه می‌دهیم. همچنین برای هر گراف $G$ ما الگوریتمی برای به‌دست آوردن یک کران پایین برای بیشترین تعداد گراف‌های شامل $G$ در یک خانواده با بعد متریک همزمان $\dim(G)$ را توصیف می‌کنیم. در ادامه، ما خانواده‌ای متشکل از دو گراف را مطالعه می‌کنیم که هر کدام از آن‌ها به وسیله جابه‌جایی یالی از دیگری بدست می‌آید. نشان داده شده است که پیدا کردن بعد متریک همزمان خانواده درخت‌ها یک مسئله NP-hard است. با این وجود، کران بالای دقیقی برای بعد متریک همزمان خانواده درخت‌ها معرفی می‌شود و در صورتی که این خانواده، از یک درخت اولیه $^8$ و توسط دنباله‌ای از جابه‌جایی‌های - یالی $^9$ حاصل شود، کران‌های بالا و پایین دقیقی بدست می‌آید.

کلمات کلیدی : بعد متریک بعد متریک همزمان مولدمتریک همزمان خانواده درخت‌ها کران‌ها