سوالی از مبحث گراف‌ها

مدیران انجمن: parse, javad123javad

ارسال پست
Mysterious_Junket_99

عضویت : چهارشنبه ۱۴۰۱/۱۰/۱۴ - ۱۴:۴۱


پست: 1



سوالی از مبحث گراف‌ها

پست توسط Mysterious_Junket_99 »

با سلام
من فارسیم زیادی خوب نیست. پس، سوال رو انگلیسی نوشتم. معذرت میخوام

vertices with least distance to subset of other vertices in a graph

تصویر

نمایه کاربر
rohamavation

نام: roham hesami radرهام حسامی راد

محل اقامت: 100 مایلی شمال لندن جاده آیلستون، لستر، لسترشر. LE2

عضویت : سه‌شنبه ۱۳۹۹/۸/۲۰ - ۰۸:۳۴


پست: 3268

سپاس: 5491

جنسیت:

تماس:

Re: سوالی از مبحث گراف‌ها

پست توسط rohamavation »

i will answer you in sweet and lovely english
2
k vertices with the smallest distance to a subset of other vertices in the graph
according to an undirected graph g=(v,e) where $e=\{e_1,e_2,...,e_m\}$ represents vertices and $v=\{v_1,v_2,...,v_n\}$ represents edges is in addition, there is a non-negative weight associated with each edge.
we have an arbitrary set of terminal nodes denoted by t, where t⊂v. for example, let $t=\{v_2,v_4,v_5,v_6\}$. considering the set t, we need to find the vertices $p (p≪|v|)$ from the set v that have the smallest distance from the set t.
in other words, let's assume p=2. first, we seek to find a vertex from the set v that has the minimum distance relative to the weight of the edges to the vertices in the set t. second, what is the second minimum vertex of v?
you can get ≪ using \ll
since g is eulerian, each vertex has even degree, and the sum of the degrees in each of its two parts is even. since g is bipartite, all of the edges are between the two parts, so removing 3 of them reduces the sum of the degrees of the vertices in each part by 3, leaving an odd total. this is possible only if at least one vertex in each part now has odd degree, in which case the new graph cannot be eulerian. (in fact the only way to remove 3 edges from an eulerian graph and not produce a vertex of odd degree is to remove a triangle of edges, which does not exist in a bipartite graph.)
در زمینه ریاضی نظریه گراف، فاصله بین دو رأس در یک گراف تعداد یال هایی است که در کوتاه ترین مسیر (که ژئودزیک گراف میگیم انها را به هم متصل می کنه. توجه داشته باشین که ممکن است بیش از یک کوتاه ترین مسیر بین دو راس وجود داشته باشد.[2] اگر هیچ مسیری وجود نداشته باشه که دو راس را به هم متصل کند، به عنوان مثال، اگر آنها به اجزای متصل مختلف تعلق داشته باشند، به طور معمول فاصله به عنوان نامحدود تعریف می شود.
در مورد یک گراف جهت دار، فاصله d(u,v) بین دو راس u و v به عنوان طول کوتاه ترین مسیر جهت دار از u تا v متشکل از کمان تعریف میشه مشروط بر اینکه حداقل یکی از این مسیرها وجود داشته باشد.نکته بعدی که برخلاف حالت گراف های بدون جهت، d(u,v) لزوماً با d(v,u) منطبق نیست - بنابراین فقط یک شبه متریک است و ممکن است این مورد در حالی تعریف شود که دیگری نیست.
خروج از مرکز ϵ(v) یک راس v بزرگترین فاصله بین v و هر راس دیگری هست
${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}$
می توان تصور کرد که یک گره چقدر از گره دورتر از گراف در نمودار فاصله داره
شعاع r یک نمودار حداقل خروج از مرکز هر رأسه
${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).}$
قطر d نمودار حداکثر خروج از مرکز هر رأس در نموداره. یعنی d بزرگترین فاصله بین هر جفت رئوسه
${\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).}$
برای پیدا کردن قطر یک نمودار ابتدا کوتاه ترین مسیر بین هر جفت رئوس را پیدا کنید. بیشترین طول هر یک از این مسیرها قطر نمودار

یک راس مرکزی در نموداری با شعاع r، رأسی است که خروج از مرکز آن r باشه یعنی راسی که فاصله آن از دورترین راس آن برابر با شعاع به طور معادل یک راس v هست به طوری که ε(v) = r.
راس محیطی در نموداری با قطر dراسیه که خروج از مرکز آن d باشد، یعنی راسی که فاصله آن از دورترین راس آن برابر با قطر باشه. یعنی v محیطی است اگر ε(v) = d.
یک راس شبه محیطی v این ویژگی را داره که برای هر راس u اگر u تا حد امکان از v دور باشد، آنگاه v تا حد امکان از u دور است. به طور رسمی، یک راس v شبه محیطی است اگر برای هر راس u با $d(u,v) = ε(v)، ϵ(u) = ϵ(v) $باشد.
ساختار سطحی نمودار با توجه به راس شروع، تقسیمی از رئوس نمودار به زیرمجموعه ها بر اساس فاصله آنها از راس شروع است.
یک گراف ژئودتیک گرافیه که هر جفت رئوس دارای کوتاه ترین مسیر منحصر به فرد است که آنها را به هم متصل می کنه
فاصله کوتاهترین مسیر وزنی، فاصله ژئودزیکی را به نمودارهای وزنی تعمیم می دهد. در این حالت فرض میشه که وزن یک یال نشان‌دهنده طول آن و فاصله وزنی کوتاه‌ترین مسیر$ dW(u,v)$ حداقل مجموع وزن‌ها در تمام مسیرهای متصله. u و v.
اثبات یک قضیه گراف
با مطالعه تئوری گراف، قضیه زیر برای راس s,t نمودار g=(v,e) و یک برش تعریف شده به عنوان "زیر مجموعه c از e یک برش s-t است اگر c = δout(u) برای برخی از زیرمجموعه u از v راضی کننده s ∈ u و t ∉ u:
حداقل طول یک مسیر s - t برابر است با حداکثر تعداد برش های s - t.
فرض کنید p کوتاه ترین مسیر s-t باشد.
پس از یک طرف، هر برش c باید حداقل یک لبه e در p داشته باشد [مطمئن شوید که دلیل آن را می بینید. بنابراین، در هر خانواده {c1,…,cm} به طوری که cj به صورت زوجی متمایز باشد، نتیجه می شود که m≤|e(p)| اجازه دهید یک یال در p حداقل در دو cj وجود داشته باشد (که با جداسازی زوجی در تضاد است).
از طرف دیگر برای هر j=1,2,…,|e(p)| اجازه دهید cj مجموعه ای از یال ها در g باشد که رئوس را دقیقاً j-1 فاصله از s از رئوس دقیقاً فاصله j از s قطع می کنند. سپس cj ناهمگن هستند و هر کدام یک برش s-t است
2
k رئوس با کمترین فاصله تا زیر مجموعه ای از رئوس دیگر در نمودار
با توجه به یک نمودار بدون جهت g=(v,e) که $e=\{e_1,e_2,...,e_m\}$ نشان دهنده رئوس و $v=\{v_1,v_2,...,v_n\}$ علاوه بر این، یک وزن غیرمنفی مرتبط با هر یال وجود دارد.
ما یک مجموعه دلخواه از گره های پایانه داریم که با t نشان داده شده است، جایی که t⊂v. برای مثال، اجازه دهید $t=\{v_2,v_4,v_5,v_6\}$. با در نظر گرفتن مجموعه t، باید رئوس $p (p≪|v|)$ از مجموعه v را پیدا کنیم که کمترین فاصله را از مجموعه t دارند.
به عبارت دیگر، p=2 را فرض کنیم. ابتدا، ما به دنبال یافتن یک راس از مجموعه v هستیم که کمترین فاصله را نسبت به وزن یال ها تا رئوس مجموعه t داشته باشد. دوم، راس حداقل دوم v چند است؟
با استفاده از \ll می توانید ≪ را دریافت کنید
از آنجایی که g اویلری است، هر راس دارای درجه زوج است و مجموع درجات هر یک از دو قسمت آن زوج است. از آنجایی که g دو قسمتی است، همه یال ها بین دو قسمت قرار دارند، بنابراین با حذف 3 تای آنها از مجموع درجات رئوس در هر قسمت 3 کاهش می یابد و مجموع فرد باقی می ماند. این تنها در صورتی امکان پذیر است که حداقل یک راس در هر قسمت اکنون دارای درجه فرد باشد، در این صورت نمودار جدید نمی تواند اویلری باشد. (در واقع تنها راه برای حذف 3 یال از یک گراف اویلری و عدم تولید یک راس با درجه فرد، حذف یک مثلث یال است که در یک گراف دوبخشی وجود ندارد.)
3
کوتاه ترین فاصله از مجموعه ای از نقاط
یک نمودار بدون وزن، بدون جهت و ساده g=(v,e) را در نظر بگیرید. ما یک زیرمجموعه s⊆v داریم و می خواهیم کوتاه ترین فاصله را از هر راس v∈v تا راس s∈s تعیین کنیم.
برای روشن بودن، هر v∈v یک بازه $d_1، d_2،\dots، d_{|s|}$دارای هر s∈s است، و ما کوچکترین مقدار از همه $d_1، d_2،\dots، d_ را می خواهیم. {|s|}$ و این کار را برای هر v∈v انجام دهید. بنابراین، برای مثال، فاصله هر s∈s 0 خواهد بود.
الگوریتم باید در زمان o(|v|+|e|) اجرا شود. توجه داشته باشید که این مستقل از |s| است است. من به اجرای همزمان bfs روی هر s∈s فکر می‌کردم و فاصله را فقط در صورتی تعیین می‌کردم که یک راس تخمین فاصله نداشته باشد (یعنی هیچ گره دیگری در s قبلاً به v نرسیده باشد). من واقعاً مطمئن نیستم که چگونه زمان اجرا را به درستی انجام دهم، زیرا برای جلوگیری از |s| ما باید bfs را در یک نقطه قطع کنیم. زمان اجرا
پاسخ
یک گره جدید s0 با لبه به همه s∈ ها (اما نه سایرین) معرفی کنید. اجرای bfs با شروع s0. مقدار مورد نظر شما s
$\quad\displaystyle \min_{s \in s} d(s, v) = d(s_0,v) - 1$
برای هر v∈v.
nota bene: این ایده به نمودارهای وزنی گسترش می یابد. باید الف) به لبه های جدید وزن 1 بدهید و ب) البته از الگوریتم ssspp استفاده کنید.
4 کوچکترین فاصله را بین دو زیر مجموعه رئوس پیدا کنید
با توجه به یک گراف بدون جهت، g=(v,e)، v1,v2 زیرمجموعه های v هستند. d(v1,v2)=min d(v1,v2)
بنابراین باید بفهمم که چگونه d(v1,v2) را در o(|v|+|e|) پیدا کنم.
d(v1,v2)=0
در غیر این صورت، من به طور تصادفی v1' را از v1 انتخاب می‌کنم و bfs(v1,v1') را اجرا می‌کنم، دورترین راس را از v1 در v1 ذخیره می‌کنم، همین کار را برای برخی از رئوس انجام می‌دهم، و از v2 تصادفی v2 را انجام می‌دهم. بازگشت d(v1,v2)=min{d(v1',v2'), d(v1',v2''),d(v1''v2''),d(v1'',v2'')}
آیا کار خواهد کرد؟ از آنجایی که زمان اجرای bfs o(|v|+|e|) است، الگوریتم پیشنهادی در o(|v|+|e|) اجرا خواهد شد.
کاری که می توانید imo انجام دهید به شرح زیر است:
مجموعه v1 را اسکن کنید و تمام لبه هایی را که از گره های v1 شروع می شوند و به گره های نه در v1 ختم می شوند، یادداشت کنید.
اکنون تمام گره های v1 را در یک گره ترکیب کنید. لبه های ذکر شده در مرحله 1 باید لبه هایی باشند که از این گره خارج می شوند.
همین کار را برای v2 انجام دهید.
این مشکل اکنون به کوتاه ترین مسیر بین گره های v1 و v2 کاهش یافته است. این را می توان با انجام یک bfs ساده در گره v1 یا v2 در o(e) که e تعداد یال های نمودار است حل کرد.
5
فاصله نمودار را ثابت کنید
برای یک نمودار g، چندین مسیر (x,y) وجود دارد. کوتاه ترین ها دارای طول 2 هستند. بنابراین d(x,y)=2. ثابت کنید که فاصله نمودار نابرابری مثلث را برآورده می کند. یعنی اگر x,y,z رئوس یک نمودار متصل g باشند، آنگاه $d(x,z)≤d(x,y)+d(y,z).$
بنابراین اساساً نمودار یک پنج ضلعی با یک راس در مرکز است. من منطق چگونگی اثبات آن را درک می کنم، اما نمی دانم چگونه آن را به عنوان یک اثبات بنویسم.
در اصل می خواستم بگویم
فرض کنید (x,z∈v) سپس d(x,z)=1 پس d(y,z)=2. بنابراین 1≤2+1 درست است.
برای حالت دیگر، فرض کنید (y,z∈v) سپس d(y,z)=1
بنابراین d(x,z)=2. بنابراین 3≤2+1 درست است.
همچنین می توانید به تعریف فضای متریک نگاه کنید، جایی که برابری مثلث همیشه برقرار است. d(x,z)≤d(x,y)+d(y,z) -
من با استفاده از یک استدلال با تناقض به این موضوع می پردازم. فرض کنید $d(x, y) + d(y, z) < d(x, z)$ طبق تعریف، d(x,y) طول کوتاه ترین مسیر از x به y و d(y,z) است. طول کوتاه ترین مسیر از y تا z است. با این حال، d(x,z) طول کوتاه ترین مسیر از x به z است، بنابراین d(x,y)+d(y,z) نمی تواند کمتر از d(x,z) باشد. بنابراین ما یک تناقض داریم.
به جای استفاده از مثال‌های خاص، به نحوه تعمیم اینجا توجه کنید. به یاد داشته باشید که یک مثال اثبات معتبری نیست، مگر اینکه از یک مثال متقابل برای رد چیزی استفاده کنید.
6 گرهی را پیدا کنید که مجموع کوتاهترین فواصل بین مجموعه ای از گره های دیگر را در یک نمودار به حداقل برساند
فرض کنید که من یک گراف بدون جهت و متصل G=(E,V) دارم که در آن E مجموعه یال‌ها را دوباره نگه می‌دارد و V مجموعه گره‌ها را دوباره نگه می‌دارد. همچنین من یک مجموعه V1⊂V دارم. هدف من یافتن یک گره $v_{target} \in V$ برای:
$\min \sum_{v \in V_1}{dis(v_{target},v)}$
که در آن $dis(v_1,v_2)$ کوتاه ترین مسیر بین v1 و v2 را محاسبه می کند.
جواب -یک روش ساده این است که از هر گره یک درخت کوتاه‌ترین مسیر جزئی بسازیم. برای هر گره منبع، می‌توانید الگوریتم دایجسترایا پریم را اعمال کنید، و زمانی که هر گره در V1 به طور دائم برچسب‌گذاری شد، به زودی پایان می‌یابد. همچنین می‌توانید بهترین گره منبع را تا کنون پیگیری کنید و زمانی که مجموع V1 حداقل مقدار فعلی باشد، یک گره منبع مشخص را خاتمه دهید.کد اون در پایتون $# Python program for Dijkstra's single
# source shortest path algorithm. The program is
# for adjacency matrix representation of the graph

# Library for INT_MAX
import sys

class Graph():

def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]

def printSolution(self, dist):
print "Vertex tDistance from Source"
for node in range(self.V):
print node,"t",dist[node]

# A utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minDistance(self, dist, sptSet):

# Initilaize minimum distance for next node
min = sys.maxint

# Search not nearest vertex not in the
# shortest path tree
for v in range(self.V):
if dist[v] < min and sptSet[v] == False:
min = dist[v]
min_index = v

return min_index

# Funtion that implements Dijkstra's single source
# shortest path algorithm for a graph represented
# using adjacency matrix representation
def dijkstra(self, src):

dist = [sys.maxint] * self.V
dist[src] = 0
sptSet = [False] * self.V

for cout in range(self.V):

# Pick the minimum distance vertex from
# the set of vertices not yet processed.
# u is always equal to src in first iteration
u = self.minDistance(dist, sptSet)

# Put the minimum distance vertex in the
# shotest path tree
sptSet = True

# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shotest path tree
for v in range(self.V):
if self.graph[v] > 0 and sptSet[v] == False and
dist[v] > dist + self.graph[v]:
dist[v] = dist + self.graph[v]

self.printSolution(dist)

# Driver program
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
];

g.dijkstra(0);

# This code is contributed by Divyanshu Mehta$
تصویر

ارسال پست