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

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

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية
{افان مات او قتل انقلبتم على اعقابكم}
2024-11-24
العبرة من السابقين
2024-11-24
تدارك الذنوب
2024-11-24
الإصرار على الذنب
2024-11-24
معنى قوله تعالى زين للناس حب الشهوات من النساء
2024-11-24
مسألتان في طلب المغفرة من الله
2024-11-24


Grid Graph  
  
2344   07:39 مساءً   date: 20-3-2022
Author : Acharya, B. D. and Gill, M. K.
Book or Source : "On the Index of Gracefulness of a Graph and the Gracefulness of Two-Dimensional Square Lattice Graphs." Indian J. Math. 23
Page and Part : ...


Read More
Date: 24-3-2022 1469
Date: 24-2-2022 1418
Date: 20-4-2022 1620

Grid Graph

 

A two-dimensional grid graph, also known as a rectangular grid graph or two-dimensional lattice graph (e.g., Acharya and Gill 1981), is an m×n lattice graph that is the graph Cartesian product P_m square P_n of path graphs on m and n vertices. The m×n grid graph is sometimes denoted L(m,n) (e.g., Acharya and Gill 1981).

GridGraph

Unfortunately, the convention on which index corresponds to width and which to height remains murky. Some authors (e.g., Acharya and Gill 1981) use the same height by width convention applied to matrix dimensioning (which also corresponds to the order in which measurements of a painting on canvas are expressed). The Wolfram Language implementation GridGraph[{mn, ...}] also adopts this ordering, returning an embedding in which m corresponds to the height and n the width. Other sources adopt the width by height convention used to measure paper, room dimensions, and windows (e.g., 8 1/2 inch by 11 inch paper is 8 1/2 inches wide and 11 inches high). Therefore, depending on convention, the graph illustrated above may be referred to either as the 7×4 grid graph or the 4×7 grid graph.

Yet another convention wrinkle is used by Harary (1994, p. 194), who does not explciitly state which index corresponds to which dimension, but uses a 0-offset numbering in defining a 2-lattice as a graph whose points are ordered pairs of integers (i,j) with i=0, 1, ..., m and j=0, 1, ..., n. If Harary's ordered pairs are interpreted as Cartesian coordinates, a grid graph with parameters m and n consists of m+1 vertices along the x-axis and n+1 along the y-axis. This is consistent with the interpretaion of P_m square P_n in the graph Cartesian product as paths with m and n edges (and hence m+1 and n+1 vertices), respectively.

The particular case of an n×n rectangular grid graph is sometimes known as a square grid graph.

Note that Brouwer et al. (1989, p. 440) use the term "m×n grid" to refer to the line graph L(K_(m,n)) of the complete bipartite graph K_(m,n), known in this work as the rook graph K_m square K_n.

Precomputed properties for a number of grid graphs are available using GraphData[{"Grid"{m, ..., r, ...}}].

A grid graph P_m square P_n has mn vertices and (m-1)n+(n-1)m=2mn-m-n edges.

A grid graph is Hamiltonian if either the number of rows or columns is even (Skiena 1990, p. 148). Grid graphs are also bipartite (Skiena 1990, p. 148). m×n and n×n grid graphs are graceful (Acharya and Gill 1981, Gallian 2018).

The numbers of directed Hamiltonian paths on the n×n grid graph for n=1, 2, ... are given by 1, 8, 40, 552, 8648, 458696, 27070560, ... (OEIS A096969). In general, the numbers of Hamiltonian paths on the m×n grid graph for fixed m are given by a linear recurrence.

The numbers of directed Hamiltonian cycles on the n×n grid graph for n=1, 2, ... are 0, 2, 0, 12, 0, 2144, 0, 9277152, ... (OEIS A143246). In general, the numbers of Hamiltonian cycles on the m×n grid graph for fixed m are given by a linear recurrence.

The numbers of (undirected) graph cycles on the n×n grid graph for n=1, 2, ... are 0, 1, 13, 213, 9349, 1222363, ... (OEIS A140517). In general the number c_k of k-cycles on the n×n grid graph is given by c_k=0 for k odd and by a quadratic polynomial in n for k even, with the first few being

c_4 = (n-1)^2

(1)

c_6 = 2(n-1)(n-2)

(2)

c_8 = {0 for n<3; 7(n-2)^2-2 otherwise

(3)

c_(10) = {0 for n<4; 4[7(n-3)^2+7(n-3)-1] otherwise

(4)

c_(12) = {0 for n<4; 76 for n=4; 2(62n^2-370n+523) otherwise

(5)

c_(14) = {0 for n<4; 32 for n=4; 1100 for n=5; 12(49n^2-338n+556) otherwise

(6)

c_(14) = {0 for n<4; 6 for n=4; 2102 for n=5; 11144 for n=6; 2(1469n^2-11452n+21395) otherwise

(7)

(E. Weisstein, Nov. 16, 2014).

The domination number of P_m square P_n is given by

 gamma(P_m square P_n)=|_((m+2)(n+2))/5_|-4

(8)

for 16<=m<=n, as conjectured by Chang (1992), confirmed up to an additive constant by Guichard (2004), and proved by Gonçalves et al. (2011). Gonçalves et al. (2011) give a piecewise formula for m<16, but the expression given for n=16 is not correct in all cases. A correct formula for n=16 attributed to Hare appears as formula (6) in Chang and Clark (1993), which however then proceeds to give an incorrect reformulation as formula (14).

GridGraphsSpecial

A generalized grid graph, also known as an n-dimensional lattice graph (e.g., Acharya and Gill 1981) can also be defined as P_m square P_n square P_r square ... (e.g., Harary 1967, p. 28; Acharya and Gill 1981). Such graphs are somtimes denoted G_(m,n,r,...) or L(m,n,r,...) (e.g., Acharya and Gill 1981). A generalized grid graph has chromatic number 2, except the degenerate case of the singleton graph, which has chromatic number 1. Special cases are illustrated above and summarized in the table below.

grid graph special case
P_1 square P_n path graph P_n
P_2 square P_n ladder graph L_n
P_2 square P_2 square graph C_4
P_2 square P_3 domino graph
P_2 square P_2 square P_2 cubical graph Q_3
P_2 square ... square P_2_()_(n) hypercube graph Q_n

P_m square P_n square P_2 is graceful (Liu et al. 2012, Gallian 2018).


 

REFERENCES

Acharya, B. D. and Gill, M. K. "On the Index of Gracefulness of a Graph and the Gracefulness of Two-Dimensional Square Lattice Graphs." Indian J. Math. 23, 81-94. 1981.

Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.

Chang, T. Y. Domination Numbers of Grid Graphs. Ph.D. thesis. Tampa, FL: University of South Florida, 1992.

Faase, F. "On the Number of Specific Spanning Subgraphs of the Graphs G square P_n." Ars Combin. 49, 129-154, 1998.

Chang, T. Y. and Clark, W. E. "The Domination Numbers of the 5×n and 6×n Grid Graphs." J. Graph Th. 17, 81-107, 1993.

Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018.

 https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gonçalves, D.; Pinlou, A.; Rao, M.; and Thomassé, S. "The Domination Number of Grids." SIAM J. Discrete Math. 25, 1443-1453, 2011.

Guichard, D. R. "A Lower Bound for the Domination Number of Complete Grid Graphs." J. Combin. Math. Combin. Comput. 49, 215-220, 2004.

Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 194, 1994.

Harary, F. "Graphical Enumeration Problems." In Graph Theory and Theoretical Physics (Ed. F. Harary). London: Academic Press, pp. 1-41, 1967.

Itai, A.; Papadimitriou, C. H.; and Szwarcfiter, J. L. "Hamilton Paths in Grid Graphs." SIAM J. Comput. 11, 676-686, 1982.

Iwashita, H.; Nakazawa, Y.; Kawahara, J.; Uno, T.; and Minato, S.-I. "Efficient Computation of the Number of Paths in a Grid Graph with Minimal Perfect Hash Functions." TCS Technical Report. No. TCS-TR-A-13-64. Hokkaido University Division of Computer Science. Apr. 26, 2013.

Jacobsen, J. L. "Exact Enumeration of Hamiltonian Circuits, Walks and Chains in Two and Three Dimensions." J. Phys. A: Math. Theor. 40, 14667-14678, 2007.

Karavaev, A. M. "FlowProblem: Hamiltonian Cycles." http://flowproblem.ru/paths/hamilton-cycles.Karavaev, A. M. "FlowProblem: Hamiltonian Paths." http://flowproblem.ru/paths/hamilton-paths.Liu, J. B.; Zou,, T.; and Lu, Y. "Gracefulness of Cartesian Product Graphs." Pure Appl. Math. (Xi'an) 28, 329-332 and 362, 2012.

Pönitz, A. "Computing Invariants in Graphs of Small Bandwidth." Math. in Computers and Sim. 49, 179-191, 1999.

Reddy, V. and Skiena, S. "Frequencies of Large Distances in Integer Lattices." Technical Report, Department of Computer Science. Stony Brook, NY: State University of New York, Stony Brook, 1989.

Schmalz, T. G.; Hite, G. E.; and Klein, D. J. "Compact Self-Avoiding Circuits on Two-Dimensional Lattices." J. Phys. A: Math. Gen. 17, 445-453, 1984.

Skiena, S. "Grid Graphs." §4.2.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 147-148, 1990.

Sloane, N. J. A. Sequences A096969, A140517, and A143246 in "The On-Line Encyclopedia of Integer Sequences."Umans, C. M. "An Algorithm for Finding Hamiltonian Cycles in Grid graphs without Holes." Undergraduate thesis.Umans, C. and Lenhart, W. "Hamiltonian Cycles in Solid Grid Graphs." In Proc. 38th Annual IEEE Sympos. Found. Comput. Sci. pp. 496-505, 1997.




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


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

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