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

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

Untitled Document
أبحث عن شيء أخر المرجع الالكتروني للمعلوماتية
القيمة الغذائية للثوم Garlic
2024-11-20
العيوب الفسيولوجية التي تصيب الثوم
2024-11-20
التربة المناسبة لزراعة الثوم
2024-11-20
البنجر (الشوندر) Garden Beet (من الزراعة الى الحصاد)
2024-11-20
الصحافة العسكرية ووظائفها
2024-11-19
الصحافة العسكرية
2024-11-19

الكاربون carbon
9-3-2018
تعريف التظلم الإداري
17-1-2023
empiricism (n.)
2023-08-22
ماص للرطوبة hygroscopic
20-3-2020
معنى كلمة سجل
21/11/2022
يؤمن التزويد الثابت من الـ ATP بفضل التحكم في التنفس
14-7-2021

Graph Path  
  
1741   03:43 مساءً   date: 11-5-2022
Author : Boesch, F. T.; Chen, S.; and McHugh, J. A. M
Book or Source : "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag
Page and Part : ...


Read More
Date: 1-4-2022 1478
Date: 26-4-2022 1522
Date: 22-7-2016 1261

Graph Path

A path in a graph G is a subgraph of G that is a path graph (West 2000, p. 20). The length of a path is the number of edges it contains.

In most contexts, a path must contain at least one edge, though in some applications (e.g., defining the path covering number), "degenerate" paths of length 0 consisting of a single vertex are allowed (Boesch et al. 1974).

An s,t-path is a path whose endpoints (vertices of degree 1) are the vertices with distinct indices s and t. (The symbols u and v are also commonly used.) A single s,t-path may be found in the Wolfram Language using FindPath[gst], while FindPath[gstkspecn] finds at most n paths of length kspec (where kspec may be Infinity and n may be All).

For a simple graph, a path is equivalent to a trail and is completely specified by an ordered sequence of vertices. For a simple graph G, a Hamiltonian path is a path that includes all vertices of G (and whose endpoints are not adjacent).

The number of (undirected) k-walks from vertex s to vertex t in a graph with adjacency matrix A is given by the (s,t) element of A^k (Festinger 1949). In order to compute the number p_k of graph paths, all closed k-walks that are not paths must be subtracted.

The first few matrices of k-paths P_k can be given in closed form by

P_1 = A

(1)

P_2 = A^2-diag(A^2)

(2)

P_3 = A^3-diag(A^2)A-Adiag(A^2)+A×A^(T)-diag(A^3)

(3)

(Luce and Perry 1949, Katz 1950, Ross and Harary 1952, Perepechko and Voropaev), where diag(A) is the matrix formed from the diagonal elements of A and × denotes matrix element-wise multiplication.

Furthermore, the number of k-cycles is related to P_k by

 c_k=1/(2k)Tr(P_(k-1)A),

(4)

where Tr denotes the trace.

Giscard et al. (2016) gave the formula for the path matrix giving the number of k-paths from i to j as

 P_k=(-1)^(k+1)sum_(H≺_(conn)G)(|N(H)|; k+1-|H|)(-1)^(|H|)A|_H^k,

(5)

where the sum is over connected induced subgraphs H of G containing both i and jN(H) denotes the number of neighbors of H in G (namely vertices v of G which are not in H and such that there exists at least one edge from v to a vertex of H), Tr denotes the matrix trace, and (A|_H^k)_(ij) is the (i,j)th element of the kth matrix power of the adjacency matrix of G restricted to the connected induced subgraph H, namely

 (A|_H)_(ij)={A_(ij)   for i,j in H; 0   otherwise,

(6)

with (i,j) in G.


REFERENCES

Boesch, F. T.; Chen, S.; and McHugh, J. A. M. "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.

Giscard, P.-L. and Rochet, P. "Enumerating Simple Paths from Connected Induced Subgraphs." 1 Jun 2016. https://arxiv.org/abs/1606.00289.

Giscard, P.-L.; Kriege, N.; and Wilson, R. C. "A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length." 16 Dec 2016. https://arxiv.org/pdf/1612.05531.pdf.

Festinger, L. "The Analysis of Sociograms Using Matrix Algebra." Human Relations 2, 153-158, 1949.

Katz, L. "An Application of Matrix Algebra to the Study of Human Relations Within Organizations." Institute of Statistics, University of North Carolina, Mimeograph Series, 1950.

Luce, R. D. and Perry, A. D. "A Method of Matrix Analysis of Group Structure." Psychometrika 14, 95-116, 1949.

Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Roberts, B. and Kroese, D. P. "Estimating the number of s-t Paths in a Graph." J. Graph Algorithms Appl. 11, 195-214, 2007.

Ross, I. C. and Harary, F. "On the Determination of Redundancies in Sociometric Chains." Psychometrika 17, 195-208, 1952.

Valiant, L. G. "The Complexity of Enumeration and Reliability Problems." SIAM J. Computing 8, 410-421, 1979.

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 20, 2000.




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


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

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