جستجو
بررسی بعد متریک همزمان خانواده گراف ها
محمداسماعیل نیکفر1
چکیده :
فرض کنید $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$ حاصل شود، کرانهای بالا و پایین دقیقی بدست میآید.
کلمات کلیدی : بعد متریک بعد متریک همزمان مولدمتریک همزمان خانواده درختها کرانها
زبان مقاله : فارسی
محل انتشار : پایان نامه کارشناسی ارشد
آدرس وب سایت کنفرانس : pre-2392277
کد IOI مقاله : ADEZ-ACAEHB
لینک مستقیم مقاله : https://isnac.ir/ADEZ-ACAEHB
نمایش چکیده انگلیسی
: https://isnac.ir/SA/ADEZ-ACAEHB
سایر مقالات ارائه دهنده
- روانشناسی و توسعه هوش مصنوعی در بستر پژوهشهای شیمی
- مطالعات و پژوهشهای ریاضی در مقطع دکترا از امکان تا تداوم
- پیشرفت در تحقیقهای ریاضی: درباره تعاریف مولد ریاضیدان
- درآمدی بر تعاریف مولد ریاضیدان با تاثیر روی تحقیقات در مقطع دکترا
- اخلاق و ریاضیات: برخی مشاهدات با تعاریف مولد ریاضیدان در تحقیقات دکترا
- مقدمه ای بر پژوهش در سال های اولیه دانشگاه و تحقیقات در مقطع دکترا
- چگونگی نگارش شفاف یک مقاله ریاضی در مقطع دکترا
- هنر و استدلال در تحقیق با ریاضیات در مقطع دکتری
- هنر و خلاقیت در استدلال ریاضی: کاوشی در اثبات و تفکر غیررسمی در پژوهشهای دکتری
- ریاضیات و اخلاق مبتنی بر تاریخ و نقش گفتگو در پژوهشهای دکتری
- طلوع هوش مصنوعی مولد در شیمی برای آموزش و پژوهش
- رویکرد پویا و شفاف در پژوهشهای دکتری ریاضی: مسیر بهبود مستمر
- زیبایی شناسی و خلاقیت در استدلال ریاضی: تحلیلی بر اثبات و اندیشه غیررسمی در تحقیقات دکتری
- جابه جایی حالت در گراف های کیلی و کاربردهای آن در مدیریت
- جابه جایی حالت بر روی گراف ها و تجزیه و تحلیل در علوم شناختی و انسانی