Walk

A walk is a sequence , , , ...,  of graph vertices  and graph edges  such that for , the edge  has endpoints  and  (West 2000, p. 20). The length of a walk is its number of edges.

A -walk is a walk with first vertex  and last vertex , where  and  are known as the endpoints. Every -walk contains a -graph path (West 2000, p. 21).

A walk is said to be closed if its endpoints are the same. The number of (undirected) closed -walks in a graph with adjacency matrix  is given by , where  denotes the matrix trace. In order to compute the number  of -cycles, all closed -walks that are not cycles must be subtracted. Similarly, to compute the number  of graph paths, all -walks that are not graph paths (because they contain redundant vertices) must be subtracted (cf. Festinger 1949, Ross and Harary 1952).

For a simple graph (which has no multiple edges), a walk may be specified completely by an ordered list of vertices (West 2000, p. 20).

A trail is a walk with no repeated edges.

---

 

REFERENCES

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

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

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

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الطبية يقدم الخدمات الصحية والعلاجية لزائري مدينة سامراء

العتبة العباسية المقدسة تقدم خدماتها لزائري مرقد الإمامين العسكريين (عليهما السلام) في سامراء

المجمَع العلمي ووفد وزارة التربية يبحثان سبل التعاون المشترك

قسم الشؤون الفكرية يصدر العدد 192 من مجلة الرياحين للأطفال

المزيد

الآخبار الصحية

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

ما لا يتوقعه أحد.. "سر غذائي" في الجبن الدسم

لتحسين الهضم والنوم.. هذا أفضل وقت لتناول العشاء

10 طرق بسيطة وغير مألوفة لحرق المزيد من السعرات يوميا

المزيد

الآخبار التكنلوجية

سابقة بعالم الطيران.. طائرة تقرر الهبوط بنفسها بعد ظرف طارئ

"الإنفلونزا الخارقة" تكتسح دول العالم.. وتثير قلقا كبيرا

مرحلة ما قبل الأعراض.. دواء جديد يستهدف "شرارة" الزهايمر

إزالة ثاني أكسيد الكربون من الغلاف الجوي.. ما دور المحيطات والبحار؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength