المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر
زكاة الغنم
2024-11-05
زكاة الغلات
2024-11-05
تربية أنواع ماشية اللحم
2024-11-05
زكاة الذهب والفضة
2024-11-05
ماشية اللحم في الولايات المتحدة الأمريكية
2024-11-05
أوجه الاستعانة بالخبير
2024-11-05

زراعة الذرة الشامية
2024-03-25
الإعفاء من الضريبة لأسباب اقتصادية
23-2-2022
Isoperimetric Problem
12-10-2018
عمل رواد الانسلاخ الحضاري
24-9-2019
Image photometry: CCD photometry
27-8-2020
Phi-Prime
26-9-2020

Graph Dimension  
  
1938   03:17 مساءً   date: 5-4-2022
Author : Buckley, F. and Harary, F.
Book or Source : "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4
Page and Part : ...


Read More
Date: 3-4-2022 1466
Date: 10-4-2022 1724
Date: 6-3-2022 1353

Graph Dimension

The dimension e(G), also called the Euclidean dimension (e.g., Buckley and Harary 1988) of a graph, is the smallest dimension n of Euclidean n-space in which G can be embedded with every edge length equal to 1 and every vertex position distinct (but where edges may cross or overlap and points may lie on edges that are not incident on them; Erdős et al. 1965).

Any connected graph with maximum vertex degree Delta has graph dimension at most Delta, with the exception of the utility graph K_(3,3) (Frankl et al. 2018). Furthermore, any graph with chromatic number k has graph dimension at most 2k. This can be seen by partitioning the space into k orthogonal two-dimensional planes, then in each plane placing the vertices with one color on a circle with radius 1/sqrt(2) centred on the plane's origin (so all points have a squared norm of 1/2) (J. Tan, pers. comm., Oct. 26, 2021).

For any nonempty graph G, the graph Cartesian product satisfies

 e(G square K_2)={e(g)   if e(G)>=2; e(G)+1   if e(G)=0 or 1

(1)

(Erdős et al. 1965, Buckley and Harary 1988). While the theorem is stated as holding for "any" graph by both references, if G is taken as the empty graph K^__n, then K^__n square K_2 is isomorphic to the ladder rung graph nP_2. Yet e(K^__n)=1 for n>1 (since vertices may not overlap by the definition of graph dimension) and e(nP_2)=1 since each of the n paths can be placed on a 1-dimensional line.

The singleton graph K_1 has graph dimension e(K_1)=0, the path graphs P_n for n>1 have graph dimension e(P_n)=1, and in general, any graph with dimension 2 or less is said to be a unit-distance graph.

The dimension of the complete graph K_n is e(K_n)=n-1 (Erdős et al. 1965, Buckley and Harary 1988). For the complete bipartite graph K_(m,n) with <=n,

 e(K_(m,n))={1   for m=n=1; 2   for m=n=2 or m=1, n>1; 3   for m=2, n>2; 4   m,n>=3

(2)

(Erdős et al. 1965, Buckley and Harary 1988).

The dimension of K_n-e is given by e(K_n-e)=n-2 for n>=3 (Erdős et al. 1965).

The hypercube graph Q_n has dimension e(Q_n)=2 for n>=2 (Erdős et al. 1965).

The wheel graph W_n has graph dimension 2 for n=7 (and hence is unit-distance) and dimension 3 otherwise (and hence is not unit-distance) (Erdős et al. 1965, Buckley and Harary 1988).

The following table summarizes the graph dimensions for various families of parametrized graphs.

graph dimension
complete bipartite graph K_(m,n) {1   for m=n=1 or mn=2; 2   for m=1, n=1, or m=n=2; 3   for min(m,n)=2; 4   otherwise
complete graph K_n n-1
cycle graph C_n 2
empty graph K^__n {0   for n=1; 1   otherwise
generalized Petersen graph GP(n,k) 2
grid graph P_k square P_m square ... {0   for k=m=...=1; 1   for km...=max(k,m,...); 2   otherwise
hypercube graph Q_n {0   for n=0; 1   for n=1; 2   otherwise
path graph P_n {0   for n=0; 1   otherwise
star graph S_n {0   for n=1; 1   for n=2,3; 3   otherwise
wheel graph W_n {2   for n=7; 3   otherwise

REFERENCES

Buckley, F. and Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4, 23-30, 1988.

Erdős, P.; Harary, F.; and Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.

Frankl, N.; Kupavskii, A.; Swanepoel, K. J. "Embedding Graphs in Euclidean Space." 12 Feb 2018. https://arxiv.org/abs/1802.03092.




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.