Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 SzegedMatrix

Source Notebook

Compute the Szeged matrix of an undirected graph or a molecule

Contributed by: Jan Mangaldan

ResourceFunction["SzegedMatrix"][g]

computes the Szeged matrix of the graph g.

ResourceFunction["SzegedMatrix"][g,"type"]

computes the Szeged matrix of the given type.

Details and Options

A Szeged matrix S is a matrix whose entries S〚i,j〛 depend on the number of vertices that are closer to vertex νi or vertex νj of the given graph.
ResourceFunction["SzegedMatrix"] assumes that the graph g is undirected and connected.
ResourceFunction["SzegedMatrix"][g] is equivalent to ResourceFunction["SzegedMatrix"][g,"Edge"].
ResourceFunction["SzegedMatrix"][g,"Edge"] gives an edge-Szeged matrix (sometimes referred to as "the" Szeged matrix), where the nonzero off-diagonal S〚i,j〛 entries correspond to edges connecting vertex νi and vertex νj in the graph.
ResourceFunction["SzegedMatrix"][g,"Path"] gives an path-Szeged matrix, where the off-diagonal S〚i,j〛 entries correspond to paths connecting vertex νi and vertex νj in the graph.
The diagonal entries of a Szeged matrix are taken to be 0.
ResourceFunction["SzegedMatrix"][g,"Edge"] gives a SparseArray object.
With the option setting "Symmetric"→False, ResourceFunction["SzegedMatrix"] gives an unsymmetric matrix whose entries S〚i,j〛 count the number of vertices that are closer to vertex νi than to vertex νj. Vertices equidistant from the two are not counted.
With the default option setting "Symmetric"→True, ResourceFunction["SzegedMatrix"] produces a symmetric matrix equivalent to the Hadamard product of an unsymmetric Szeged matrix with its transpose.
ResourceFunction["SzegedMatrix"][mol,"type"] computes the Szeged matrix of a molecule mol, where the hydrogens are ignored by default. Use the option setting IncludeHydrogens→All to account for hydrogens.
ResourceFunction["SzegedMatrix"][entity,"type"] computes the Szeged matrix of an entity of type "Chemical" or "Graph".

Examples

Basic Examples (3) 

A graph:

In[1]:=
g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 5 <-> 6, 6 <-> 7, 6 <-> 3}]
Out[1]=

The Szeged matrix of the graph:

In[2]:=
ResourceFunction["SzegedMatrix"][g] // MatrixForm
Out[2]=

The path-Szeged matrix of the graph:

In[3]:=
ResourceFunction["SzegedMatrix"][g, "Path"] // MatrixForm
Out[3]=

Scope (2) 

Compute the Szeged matrix of a molecule:

In[4]:=
ResourceFunction["SzegedMatrix"][ Molecule[{"C", "C", "C", "C", "C", "C", "C", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H", "H"}, { Bond[{1, 2}, "Single"], Bond[{2, 3}, "Single"], Bond[{3, 4}, "Single"], Bond[{4, 5}, "Single"], Bond[{5, 6}, "Single"], Bond[{6, 7}, "Single"], Bond[{6, 1}, "Single"], Bond[{7, 3}, "Single"], Bond[{1, 8}, "Single"], Bond[{1, 9}, "Single"], Bond[{2, 10}, "Single"], Bond[{2, 11}, "Single"], Bond[{3, 12}, "Single"], Bond[{4, 13}, "Single"], Bond[{4, 14}, "Single"], Bond[{5, 15}, "Single"], Bond[{5, 16}, "Single"], Bond[{6, 17}, "Single"], Bond[{7, 18}, "Single"], Bond[{7, 19}, "Single"]}, {}]]
Out[4]=

Compute the Szeged matrix of a named entity:

In[5]:=
ResourceFunction["SzegedMatrix"][Entity["Graph", "TutteGraph"]]
Out[5]=

Options (5) 

IncludeHydrogens (2) 

By default, hydrogens are ignored in the computation of the Szeged matrix:

In[6]:=
ResourceFunction["SzegedMatrix"][Molecule["neopentane"]]
Out[6]=

Use IncludeHydrogens→All to account for hydrogens:

In[7]:=
ResourceFunction["SzegedMatrix"][Molecule["neopentane"], IncludeHydrogens -> All]
Out[7]=

Symmetric (3) 

A graph:

In[8]:=
g = \!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5, 6, 7}, {Null, {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, { 6, 3}}}]]}, TagBox[GraphicsGroupBox[ GraphicsComplexBox[{{3.9663918903831314`, 1.0919291762496157`}, {3.0207808082288583`, 0.9552945327016871}, {1.857646907887559, 0.7760448189916244}, {1.3246326545959364`, 0.}, { 0.5258555066054988, 0.2091905594672936}, { 0.7496124889177228, 1.0815058716728898`}, {0., 1.7448440546333561`}}, { {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[0.], ArrowBox[{{1, 2}, {2, 3}, {3, 4}, {3, 6}, {4, 5}, {5, 6}, {6, 7}}, 0.03679069204342064]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.03679069204342064], DiskBox[2, 0.03679069204342064], DiskBox[3, 0.03679069204342064], DiskBox[4, 0.03679069204342064], DiskBox[5, 0.03679069204342064], DiskBox[6, 0.03679069204342064], DiskBox[7, 0.03679069204342064]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None]\);

Compare the symmetric and unsymmetric forms of the edge-Szeged matrices:

In[9]:=
MatrixForm /@ {ResourceFunction["SzegedMatrix"][g, "Edge", "Symmetric" -> True], ResourceFunction["SzegedMatrix"][g, "Edge", "Symmetric" -> False]}
Out[9]=

Compare the symmetric and unsymmetric forms of the path-Szeged matrices:

In[10]:=
MatrixForm /@ {ResourceFunction["SzegedMatrix"][g, "Path", "Symmetric" -> True], ResourceFunction["SzegedMatrix"][g, "Path", "Symmetric" -> False]}
Out[10]=

Applications (3) 

Compute the Szeged index of a graph:

In[11]:=
SzegedIndex[g_] := Total[ResourceFunction["SzegedMatrix"][g], 2]/2

For acyclic graphs, the Szeged index coincides with the Wiener index:

In[12]:=
g = GraphData[{"CompleteTree", {2, 3}}]
Out[12]=
In[13]:=
{SzegedIndex[g], GraphData[{"CompleteTree", {2, 3}}, "WienerIndex"]}
Out[13]=

For graphs with cycles, equality no longer holds:

In[14]:=
g = GraphData["UtilityGraph"]
Out[14]=
In[15]:=
{SzegedIndex[g], GraphData["UtilityGraph", "WienerIndex"]}
Out[15]=

Properties and Relations (2) 

The edge-Szeged matrix is equal to the Hadamard product of the path-Szeged matrix and the adjacency matrix:

In[16]:=
g = \!\(\* GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5, 6, 7}, {Null, {{1, 2}, {2, 3}, {3, 4}, {3, 5}, {5, 6}, {5, 7}}}]]}, TagBox[GraphicsGroupBox[ GraphicsComplexBox[{{0., 0.}, {0., 0.8401680504168059}, { 0.8401680504168059, 1.6803361008336117`}, { 0.8401680504168059, 0.8401680504168059}, { 1.6803361008336117`, 0.8401680504168059}, { 1.260252075625209, 0.}, {2.100420126042015, 0.}}, { {Hue[0.6, 0.7, 0.5], Opacity[0.7], Arrowheads[0.], ArrowBox[{{1, 2}, {2, 3}, {3, 4}, {3, 5}, {5, 6}, {5, 7}}, 0.023421087284658304`]}, {Hue[0.6, 0.2, 0.8], EdgeForm[{GrayLevel[0], Opacity[0.7]}], DiskBox[1, 0.023421087284658304], DiskBox[2, 0.023421087284658304], DiskBox[3, 0.023421087284658304], DiskBox[4, 0.023421087284658304], DiskBox[5, 0.023421087284658304], DiskBox[6, 0.023421087284658304], DiskBox[7, 0.023421087284658304]}}]], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False]], DefaultBaseStyle->"NetworkGraphics", FormatType->TraditionalForm, FrameTicks->None]\); ResourceFunction["SzegedMatrix"][g, "Edge"] == ResourceFunction["SzegedMatrix"][g, "Path"]*AdjacencyMatrix[g]
Out[17]=

A symmetric Szeged matrix is equal to the Hadamard product of an unsymmetric Szeged matrix with its transpose:

In[18]:=
um = ResourceFunction["SzegedMatrix"][g, "Edge", "Symmetric" -> False]; sm = ResourceFunction["SzegedMatrix"][g, "Edge", "Symmetric" -> True]; sm == um*Transpose[um]
Out[19]=

Requirements

Wolfram Language 12.3 (May 2021) or above

Version History

  • 1.0.0 – 15 December 2023

Source Metadata

  • Citation:
    • Gutman I., "A formula for the Wiener number of trees and its extension to graphs containing cycles." Graph Theory Notes of New York, vol. 27, no. 2, 9–15, 1994.
    • Gutman I., Dobrynin A.A., "The Szeged index - A success story." Graph Theory Notes of New York, vol. 34, no. 1, 37–44, 1998.
    • Diudea M.V., Minailiuc O.M., Katona G., Gutman I., "Szeged Matrices and Related Numbers." MATCH Communications in Mathematical and in Computer Chemistry, vol. 35, 129–143, 1997.
      Available from       https://match.pmf.kg.ac.rs/electronic_versions/Match35/match35_129-143.pdf

Related Resources

License Information